LeetCode 94. 二叉树的中序遍历（中）

常见的二叉树操作，用循环和递归两种方式进行中序遍历（左 -> 中 -> 右）。

题目

给定一个二叉树，返回它的 中序 遍历。
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
注意: 输入不一定是二叉搜索树。

示例

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

考察知识点

二叉树

核心思想

方法一、递归调用

  • 保存根节点在 res 中。
  • 传入左节点递归，将结果保存在 left 中。
  • 传入右节点递归，将结果保存在 right 中。
  • 返回 [left, res, right]

方法二、循环方法

  • 把当前节点的所有左侧子结点压入栈
  • 访问节点，处理该节点的右子树
    • 由于之前把左子树先压入了，所以这里先弹出左子树节点
    • 然后设置新的 node 为右子树，下一次 while 循环就会去处理右子树了。这样一来就实现了 "左 -> 根 -> 右" 的顺序。

Python版本

  • 方法一的实现
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        """
        In-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        if not root:  return []  # 空节点
        res = [root.val]
        left_tree = self.inorderTraversal(root.left)
        right_tree = self.inorderTraversal(root.right)
        return left_tree + res + right_tree
  • 方法二的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def inorderTraversal(self, root):
        """
        In-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        res = []
        stack = []
        node = root
        while node or len(stack) > 0:
            while node:  # 把当前节点的所有左侧子结点压入栈 
                stack.append(node)
                node = node.left
            if len(stack):  # 访问节点，处理该节点的右子树
                node = stack.pop()  # 由于之前把左子树先压入了，所以这里先弹出左子树节点
                res.append(node.val)
                node = node.right  #  然后设置新的node为右子树，下一次while循环就会去处理右子树了。这样一来就实现了左 -> 根 -> 右 的顺序。
        return res