二叉树算法总结

几种遍历算法：

  1. Pre-Order 前序：
    1. 生成一条搜索路径。因为父节点永远先被操作。
    2. 第一次访问就输出数据。
    3. 可以用来实现目录结构的展示。
  2. In-Order 中序:
    1. （二叉树）特点是遍历顺序从小到大：要求排序的情形。
    2. 中缀表达式。
  3. Post-Order 后序:
    1. 在执行操作时，已经遍历过该节点的子节点：进行破坏性操作：比如删除节点。
    2. 目录文件大小计算。
    3. 后缀表达式。
  4. BFS 广度优先：
    1. 层序遍历。
    2. 最短路径。
    3. 树很高。
  5. DFS 深度优先：
    1. 树很胖。
class Solution:
   def postorderTraversal(self, root: TreeNode) -> List[int]:
      res, stack = [], [(root, False)]
      while stack:
         node, visited = stack.pop()  # the last element
         if node:
               if visited:
                  res.append(node.val)
               else:  # postorder: left -> right -> root
                  stack.append((node, True))
                  stack.append((node.right, False))
                  stack.append((node.left, False))
      return res

参考:

  1. Go Further Blog

  2. Leetcode Discussion - 三种遍历算法的一般解法（用一个tuple记录是否visit过）

插入/删除

Insertion without balancing the tree. (Easy)

Start from the root, walk the tree until we find a NIL pointer, insert the new value there.

Deletion. (Tricky)

Say we want to delete node z, This operation has three basic cases:

  1. z has no children: we simply delete the z by replacing it with NIL.

  2. z only has one child(either left or right): we replace z with the only child.

  3. z has both left child and right child: then we find z’s successor y — which must be in z’s right subtree — and have y take z’s position in the tree. The rest of z’s original right subtree becomes y’s new right subtree, and z’s left subtree becomes y’s new left subtree. This case is tricky because it matters whether y is z’s right child.

    • If y is z’s right child, then we replace z by y, leaving y’s right child alone.
    • Otherwise, y lies within z’s right subtree but is not z’s right child (part (d)). In this case, we first replace y by its own right child, and then we replace z by y.
· 面试笔记