Tree & Search

树以及树搜索算法

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

Binary Tree

Tree Representation

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

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)

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

算法题集锦: