Binary Tree Traversal

此内容尚不支持你的语言。

The binary tree node is defined as follows:

1
class TreeNode:
2
    def __init__(self, x: int):
3
        self.val = x
4
        self.left = None
5
        self.right = None

Inorder Traversal

In inorder traversal, the parent node is in between its left and right child nodes. The idea is to first traverse to the leftmost node and then process the node itself, followed by processing its right child node.

1
def inorder(root):
2
    ans = []
3
    stack = []
4
    cur = root
5

6
    while stack or cur:
7
        # iterate through the tree until reaching the leftmost node
8
        while cur:
9
            stack.append(cur)
10
            cur = cur.left
11
        cur = stack.pop()
12
        ans.append(cur.val)
13
        cur = cur.right
14
    return ans

Preorder Traversal

In preorder traversal, the parent node is processed first followed by its left and right child nodes.

\text{node}\to \text{left}\to \text{right}

We can implement it using a stack. As we iterate through the tree, first process the node itself, then append its child nodes to the stack. Note that in order to ensure the left child node is processed first, we need to append the right child node first.

1
def preorder(root):
2
    ans = []
3
    if root is None:
4
        return ans
5
    stack = [root]
6

7
    while stack:
8
        cur = stack.pop()
9
        ans.append(cur.val)
10
        # append right child first so that left child is processed first
11
        if cur.right:
12
            stack.append(cur.right)
13
        if cur.left:
14
            stack.append(cur.left)
15
    return ans

Postorder Traversal

Postorder traversal can be implemented in a similar fashion as preorder traversal. Notice that in preorder traversal, we process the node itself followed by its left and right child nodes.

\text{node}\to \text{left}\to \text{right}

In postorder traversal, we process its left and right child nodes first, followed by the node itself.

\text{left}\to \text{right}\to \text{node}

Therefore we can reuse the implementation of preorder traversal, and the only difference is that we need to reverse the order when recording values. One way to do so is, instead of appending the node value at the end of the result list, we insert it at the beginning.

1
def postorder(root):
2
    if not root:
3
        return []
4
    stack = [root]
5
    result = []
6

7
    while stack:
8
        node = stack.pop()
9
        result.insert(0, node.val) # reverse the process of preorder
10
        # append left child first so that right child is processed first
11
        if node.left:
12
            stack.append(node.left)
13
        if node.right:
14
            stack.append(node.right)
15
    return result

Or process the values first and then reverse the result list at the end.

1
def postorder(root):
2
    if not root:
3
        return []
4
    stack = [root]
5
    result = []
6

7
    while stack:
8
        node = stack.pop()
9
        result.insert(0, node.val) # reverse the process of preorder
10
        result.append(node.val)
11
        # append left child first so that right child is processed first
12
        if node.left:
13
            stack.append(node.left)
14
        if node.right:
15
            stack.append(node.right)
16
    return result
17
    return result[::-1]