[145][困难] 二叉树的后序遍历

题目描述

145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3

输出: [3,2,1]

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

解题思路

递归

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)

        dfs(root)
        return res

迭代

后续遍历顺序是左右中. 但如果我们按中右左的形式遍历, 得到的结果会与后续遍历的结果完全相反, 只需要将这种遍历方式得到的数组反转, 即得到后续遍历的结果.

前序遍历顺序是中左右, 与中右左相比只是先左和先右的问题, 参考[144][中等] 二叉树的前序遍历的迭代方法.

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        res, stack = [], [root]
        while stack:
            node = stack.pop(-1)

            res.append(node.val)
            if node.left is not None:
                stack.append(node.left)
            if node.right is not None:
                stack.append(node.right)
        return res[::-1]