原題

給出一棵二叉樹，返回其節(jié)點(diǎn)值的后序遍歷。

給出一棵二叉樹 {1,#,2,3}

   1
    \
     2
    /
   3

返回 [3,2,1]

解題思路

• 遞歸求解，定義一個(gè)helper函數(shù)，定義一個(gè)result全局變量，傳入helper函數(shù)
• Divide & Conquer

完整代碼

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

# 方法一
class Solution:
    """
    @param root: The root of binary tree.
    @return: Postorder in ArrayList which contains node values.
    """
    def postorderTraversal(self, root):
        res = []
        self.helper(root, res)
        return res
            
    def helper(self, root, result):
        if root:
            self.helper(root.left, result)
            self.helper(root.right, result)
            result.append(root.val)

# 方法二
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)
        
        res += left
        res += right
        res.append(root.val)
        return res