Tree-based DFS

Posted on | In
Summary of DFS.

Tree-based DFS

Basically, there are four ways to traverse a Tree:

  1. Level order
  2. Pre order
  3. In order
  4. Post order

We can use BFS to get the level order traversal. However, we need DFS to get the other three orders of traversal.

Traversal

fig. 1

  1. Level order (BFS)
  2. Pre order (root->left tree->right tree)

ABDECF

1
2
3
4
5
6
def pre_order(root, result): # recursion
    if root is None:
         return
    result.append(root.val)
    traverse(root.left, result)
    traverse(root.right, result)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def preorder_non_recursion(root):
    stack = []
    preorder = []
    if not root:
        return preorder
    stack.append(root)
    while len(stack) > 0:
        node = stack.pop()
        preorder.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return preorder
  1. In order (left tree->root->right tree)

DBEAFC

⭐️中序遍历是一个升序序列

1
2
3
4
5
6
def in_order(root, result): # recursion
    if root is None:
        return
    traverse(root.left, result)
    result.append(root.val)
    traverse(root.right, result)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def inorderTraversal(root): # iteration
    stack = []
    result = []

    while root:
        stack.append(root)
        root = root.left
    
    while len(stack) > 0:
        node = stack[-1]
        result.append(node.val)
        if not node.right: # if node.right is None
            node = stack.pop()
            while len(stack) > 0 and stack[-1].right == node:
                node = stack.pop()
        else:
            node = node.right
            while node:
                stack.append(node)
                node = node.left
    return result
  1. Post order

DEBFCA

1
2
3
4
5
6
def post_order(root, result): # recursion
    if root is None:
        return
    traverse(root.left, result)
    traverse(root.right, result)
    result.append(root.val)

Binary Tree三大考点

求值，求路径

结构变化

BST