博客

给定一个二叉树，返回它的

后序

遍历。

示例:

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

输出: [3,2,1]

第一种思路:

递归，先处理子树再把node.val加进去。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

第二种思路：

迭代，

按照根节点，左节点，右节点的顺序入栈，

然后逐个添加到res的头部。

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

第三种思路：

迭代，

既然后序遍历的顺序是左右中，那么自然地想，可不可以先算出中右左的遍历，然后逆转结果得到后序遍历的结果呢。

测试发现是可行的，以下代码是在

LeetCode-Python-144. 二叉树的前序遍历

的基础上修改的。

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