原题
给出一棵二叉树，返回其节点值的后序遍历。
给出一棵二叉树 {1,#,2,3}
1
\
2
/
3
返回 [3,2,1]
解题思路
- 递归求解，定义一个helper函数，定义一个result全局变量，传入helper函数
- 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
