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）则所有操作的复杂度为 θ(logn)\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)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)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)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

算法题集锦：

PreviousGraph & SearchNextWeighted Shortest Paths

Last updated