二叉树的中序遍历

发表于 更新于 分类于 阅读次数：

二叉树的中序遍历（难度：中等）

1579622453083

中序遍历：左-中-右

方法一：递归

定义一个辅助函数来实现递归。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode root, List < Integer > res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }
}

复杂度

时间复杂度：O(n)。递归函数 T(n) = 2 T(n/2)+1。 空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。

方法二：迭代

颜色标记法：

作者：hzhu212 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/ 来源：力扣（LeetCode）

其核心思想如下：

  • 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
  • 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
  • 如果遇到的节点为灰色，则将节点的值输出。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node == None:
                continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

如要实现前序、后序遍历，只需要调整左右子节点的入栈顺序即可。

另一种写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                return res
            root = stack.pop()
            res.append(root.val)
            root = root.right
1579622422214
复杂度

时间复杂度：O(n)。

空间复杂度：O(n)。

算法 执行用时 内存消耗 语言
方法二：迭代（另一种写法） 28 ms 13 MB Python3
方法二：迭代（颜色标价法） 36 ms 12.7 MB Python3
方法一：递归 0 ms 34.6 MB Java