145._binary_tree_postorder_traversal.md

145. Binary Tree Postorder Traversal 二叉树的后序遍历

难度: 困难

刷题内容

原题连接

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

内容描述

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

示例:

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

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题方案

思路 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题是一样的思路

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

        return res[::-1]