0094：二叉树的中序遍历

力扣第 94 题

题目

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

分析

• 对于树，有个通用的遍历方法：
  • 初始栈保存根节点
  • 每轮出栈，如果是节点，按 [右子树、节点值、左子树] 顺序入栈
  • 如果出栈的是节点值，说明其左子树已经遍历完，将节点值添加到结果中
  • 依此循环直到栈空即遍历完毕
• 前/后序遍历只需改变 右子树、节点值、左子树 的入栈顺序即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res,sk = [],[root]
        while sk:
            p = sk.pop()
            if isinstance(p,int):
                res.append(p)
            elif p:
                sk.extend([p.right,p.val,p.left])
        return res

37 ms