目录

0145:二叉树的后序遍历

力扣第 145 题

题目

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

示例 1:

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

示例 2:

输入:root = []
输出:[]

示例 3:

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

提示:

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

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

相似问题:

分析

迭代算法类似 0094,入栈顺序换成 [节点值、右子树、左子树] 即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res,sk = [],[root] if root else []
        while sk:
            u = sk.pop()
            if isinstance(u,int):
                res.append(u)
            elif u:
                sk.extend([u.val,u.right,u.left])
        return res

37 ms