莫非 - 技术博客
0%

二叉树遍历详解

发表于 更新于 分类于
二叉树遍历有前序、中序、后序、层序四种遍历方式。有递归、迭代、Morris三种不同的解法。

二叉树遍历有前序、中序、后序、层序四种遍历方式。

递归解法

先序遍历

1
2
3
4
5
6
7
8
9
10
11
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    def postorder(node):
        if node is None:
            return
        res.append(node.val)
        postorder(node.left)
        postorder(node.right)

    res = []
    postorder(root)
    return res

中序遍历

1
2
3
4
5
6
7
8
9
10
11
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    def inorder(node):
        if node is None:
            return
        inorder(node.left)
        res.append(node.val)
        inorder(node.right)

    res = []
    inorder(root)
    return res

后序遍历

1
2
3
4
5
6
7
8
9
10
11
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    def postorder(node):
        if node is None:
            return
        postorder(node.left)
        postorder(node.right)
        res.append(node.val)

    res = []
    postorder(root)
    return res

迭代解法

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    stack = []
    node = root
    while node or stack:
        while node:
            res.append(node.val)
            stack.append(node)
            node = node.left
        node = stack.pop()
        node = node.right
    return res

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    res = []
    stack = [(root, 0)]
    while stack:
        node, flag = stack.pop()
        if flag == 0:
            if node.right:
                stack.append((node.right, 0))
            stack.append((node, 1))
            if node.left:
                stack.append((node.left, 0))
        else:
            res.append(node.val)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        res.append(node.val)
        node = node.right
    return res

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    res = []
    stack = [(root, 0)]
    while stack:
        node, flag = stack.pop()
        if flag == 0:
            stack.append((node, 1))
            if node.right:
                stack.append((node.right, 0))
            if node.left:
                stack.append((node.left, 0))
        else:
            res.append(node.val)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    stack = []
    node = root
    while node or stack:
        while node:
            res.append(node.val)
            stack.append(node)
            node = node.right
        node = stack.pop()
        node = node.left
    return res[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    stack = []
    node = root
    last_visit = None
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack[-1]
        if node.right is None or node.right == last_visit:
            stack.pop()
            res.append(node.val)
            last_visit = node
            node = None
        else:
            node = node.right
    return res

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def levelOrder(self, root: TreeNode) -> List[List[int]]:
    if root is None:
        return []
    queue = [root]
    res = []
    while queue:
        result.append([])
        next_queue = []
        for node in queue:
            res[-1].append(node.val)
            if node.left:
                next_queue.append(node.left)
            if node.right:
                next_queue.append(node.right)
        queue = next_queue
    return res

Morris解法

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    cur = root
    res = []
    while cur:
        right_most = cur.left
        if right_most is None:
            res.append(cur.val)
            cur = cur.right
            continue
        while right_most.right and right_most.right != cur:
            right_most = right_most.right
        if right_most.right is None:
            res.append(cur.val)
            right_most.right = cur
            cur = cur.left
        else:
            right_most.right = None
    return res

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    cur = root
    res = []
    while cur:
        right_most = cur.left
        if right_most is None:
            res.append(cur.val)
            cur = cur.right
            continue
        while right_most.right and right_most.right != cur:
            right_most = right_most.right
        if right_most.right is None:
            right_most.right = cur
            cur = cur.left
        else:
            right_most.right = None
            res.append(cur.val)
            cur = cur.right
    return res

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    cur = root
    res = []
    while cur:
        left_most = cur.right
        if left_most is None:
            res.append(cur.val)
            cur = cur.left
            continue
        while left_most.left and left_most.left != cur:
            left_most = left_most.left
        if left_most.left is None:
            res.append(cur.val)
            left_most.left = cur
            cur = cur.right
        else:
            left_most.left = None
            cur = cur.left
    return res[::-1]

参考

二叉树遍历(先序、中序、后序) - 简书 (jianshu.com)

图解 二叉树的四种遍历 - 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

史上最全遍历二叉树详解 - 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)