0145._binary_tree_postorder_traversal.md

145. Binary Tree Postorder Traversal

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/binary-tree-postorder-traversal/description/

内容描述

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?

解题方案

思路 1

递归，so easy

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        
        left = self.postorderTraversal(root.left)
        right = self.postorderTraversal(root.right)
        
        if left:
            res.extend(left)
        if right:
            res.extend(right)

        res.append(root.val)
        return res

思路 2

也可以先写一下后序遍历的函数，然后一个一个贴上去

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def postOrder(root):
            if not root : return
            postOrder(root.left)
            postOrder(root.right)
            res.append(root.val)
            
        res = []
        postOrder(root)
        return res

思路 3

迭代, 其实思路就一句话，后序遍历是左右中，因为我们第一个放进去的肯定是中（即root），所以我们逆向思维考虑一下，我们按照中右左的顺序放进去，然后返回res[::-1]就行了。这其实跟leetcode第144题是一样的思路

beats 99.67%

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        
        res, stack = [], [root]
        
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

        return res[::-1]