Tree

basic

• Root: The node at the top of the tree.
• Parent: When any node (except the root) has exactly one edge running upward to another node. The node above is called parent of the node.
• Child: Any node may have one or more lines running downward to other nodes. These nodes below the given node called its children.
• Leaf: A node that has no children is called a leaf. There can be only one root in a tree but there can be many leaves.
• Level (Height): the level of a particular node refers to how many generations the node is from the root. The root is at level 0 and its children are at level 1 and so on.

思想

重点就是把握树的递归特性。题目要想办法改变成对于左右子树的子问题。binary tree: node with left and right child

• 深度问题: 整棵树的深度可以看成右子树的深度与左子树的深度的最大值
• 长度问题：左右子树最大值加上中心节点
• 颠倒：左子树和右子树分别交换自己，最后根节点交换左右子树
• merge:类似链表merge
• 判断是否相同。左右子树分别判断
• BST valid: 设定左右子树的上下限
• 可以利用binary search 分解题目

遍历

Algorithm Inorder(tree)

1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Algorithm Preorder(tree)

1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)

Algorithm Postorder(tree)

1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.

---

Backlinks

• Algo (my_note)