前往此题

解题思路

按照后序遍历左子节点->右子节点->根节点的顺序来，下图的最终结果就是4 5 2 6 7 3 1

递归法

递归法十分简单，直接套模板即可

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


    def dfs(self, root, res):
        if not root: return

        self.dfs(root.left, res)
        self.dfs(root.right, res)
        res.append(root.val)

迭代法

算法过程

1. 初始化栈stack,将根节点root入栈
2. 如果左子节点非空，将左子节点入栈
3. 如果右子节点非空，将右子节点入栈
4. 最后将root的值放入结果res中
5. 最终返回倒序的res

代码

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

        while stack:
            cur = stack.pop()
            if cur.left:stack.append(cur.left)
            if cur.right:stack.append(cur.right)
            res.append(cur.val)
        
        return res[::-1]