# Tree & Search 本节内容为自己整理，是 Graph & Search 的子集。示例中皆假设不同节点的值不同。 ## Binary Tree ### Tree Representation ```python class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None ``` ### Tree Search #### Depth First Search (DFS) 方法 1：使用递归 ```python def dfs(root): if not root: return # preorder: action on root.val left_val = dfs(root.left) # inorder: action on root.val right_val = dfs(root.right # postorder: action on root.val return func(left_val, right_val) ``` 方法 2：使用栈迭代 ```python def dfs_preorder(node): if not node: return stack = [node] while stack: node = stack.pop() # from right to left if node.right: stack.append(node.right) if node.left: stack.append(node.left) def dfs_postorder(node): if not node: return stack = [node] ret = [] while stack: node = stack.pop() ret.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return ret[::-1] ``` #### Breadth First Search (BFS) 方法1：使用 list ```python def bfs(root): if not root: return q = [root] while q: nq = [] for node in q: if node.left: nq.append(node.left) if node.right: nq.append(node.right) q = nq ``` 方法2：使用 dequeue ```python from collections import dequeue def bfs(root): if not root: return q = dequeue([root]) while q: node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) ``` ### Binary Search Tree (BST) BST 是一种特殊的 Binary Tree，其中任意节点都满足： * 左子树中所有节点的值都小于当前节点的值 * 右子树中所有节点的值都大于当前节点的值 BST 的一些特性罗列如下： * 通过 in-order traversal 可以得到所有节点按 key 排序的结果 * 擅长做一些特殊查询 * 查询与某 key 大小最相近的元素（closest lower/greater elements） * 区间查询（range queries） * 如果是 Self-Balancing BST（Red-Black Tree, AVL Tree, Splay Tree）则所有操作的复杂度为 $$\theta(logn)$$ #### Search ```python def search(root, key): if root is None or root.val == key: return root if root.val < key: return search(root.right, key) return search(root.left, key) ``` Time complexity: $$O(h)$$ #### Insertion ```python def insert(root, node): if root is None: root = node else: if roo.val < node.val: if root.right is None: root.right = node else: insert(root.right, node) else: if root.left is None: root.left = node else: insert(root.left, node) ``` Time complexity: $$O(h)$$ #### Deletion 删除的时候分三种情况考虑： 1. 如果是 leaf node：直接删除 2. 如果只有一个 child：交换两个节点的值，并把 child node 删了 3. 如果有两个 children：找到 inorder 遍历的下一个 node，交换两个节点的值，并把下一个 node 删除 ```python # Given a non-empty binary search tree, return the node # with minimum key value found in that tree. def minValueNode(node): current = node while current.left is not None: current = current.left return current def deleteNode(root, key): if root is None: return root if key < root.key: root.left = deleteNode(root.left, key) elif key > root.key: root.right = deleteNode(root.right, key) else: if root.left is None: root = root.right return root elif root.right is None: root = root.left return root next_node = minValueNode(root.right) root.key = next_node.key root.right = deleteNode(root.right, next_node.key) return root ``` Time complexity: $$O(h)$$ #### Traversal * In-order traversal of BST always produces sorted output * we can construct a BST with only Preorder or Postorder or Level Order traversal. * number of unique BSTs with n distinct keys is Catalan Number #### 算法题集锦： * Search * [Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/) * Pre-order Traversal * [Print Binary Tree](https://leetcode.com/problems/print-binary-tree/) * [Maximum Binary Tree](https://leetcode.com/problems/maximum-binary-tree/) * [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) * [Binary Tree Paths](https://leetcode.com/problems/binary-tree-paths/) * [Second Minimum Node In a Binary Tree](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/) * [Find Mode in Binary Search Tree](https://leetcode.com/problems/find-mode-in-binary-search-tree/) * [Verify Preorder Serialization of a Binary Tree](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/) * [Merge Two Binary Trees](https://leetcode.com/problems/merge-two-binary-trees/) * [Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) * In-order Traversal * [Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/) * [Binary Tree In-order Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) * [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) * [Increasing Order SearchTree](https://leetcode.com/problems/increasing-order-search-tree) * Post-order Traversal: * [Binary Tree Tilt](https://leetcode.com/problems/binary-tree-tilt/) * [Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/) * [Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/) * [Binary Tree Cameras](https://leetcode.com/problems/binary-tree-cameras/) * [Binary Tree Pruning](https://leetcode.com/problems/binary-tree-pruning/) * [Unique Binary Search Trees II](https://leetcode.com/problems/unique-binary-search-trees-ii/) * [Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/) * Breadth First/Level Order Search * [Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/) * [Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/) * [Binary Tree Level Order Traversal II](https://leetcode.com/problems/binary-tree-level-order-traversal-ii/) * Construction * [Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/) * [Construct Binary Tree from In-order and Post-order Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/) * Complete Tree * [Count Complete Tree Node](https://leetcode.com/problems/count-complete-tree-nodes/) * Dynamic Programming * [Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/) * Graph Search * [All Nodes Distance K in Binary Tree](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/)