Tree & Search

树以及树搜索算法

本节内容为自己整理，是 Graph & Search 的子集。示例中皆假设不同节点的值不同。

Binary Tree

Tree Representation

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Tree Search

Depth First Search (DFS)

方法 1：使用递归

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：使用栈迭代

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

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

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

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

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 删除

# 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
• Pre-order Traversal

  • Print Binary Tree
  • Maximum Binary Tree
  • Invert Binary Tree
  • Binary Tree Paths
  • Second Minimum Node In a Binary Tree
  • Find Mode in Binary Search Tree
  • Verify Preorder Serialization of a Binary Tree
  • Merge Two Binary Trees
  • Binary Tree Preorder Traversal
• In-order Traversal

  • Flatten Binary Tree to Linked List
  • Binary Tree In-order Traversal
  • Validate Binary Search Tree
  • Increasing Order SearchTree
• Post-order Traversal:

  • Binary Tree Tilt
  • Univalued Binary Tree
  • Diameter of Binary Tree
  • Binary Tree Cameras
  • Binary Tree Pruning
  • Unique Binary Search Trees II
  • Binary Tree Maximum Path Sum
• Breadth First/Level Order Search

  • Maximum Width of Binary Tree
  • Binary Tree Right Side View
  • Binary Tree Level Order Traversal II
• Construction

  • Convert Sorted List to Binary Search Tree
  • Construct Binary Tree from In-order and Post-order Traversal
• Complete Tree

  • Count Complete Tree Node
• Dynamic Programming

  • Unique Binary Search Trees
• Graph Search

  • All Nodes Distance K in Binary Tree