原題
給出一棵二叉樹姑裂，返回其節(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
