目录

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