145. Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
First
Stack
同样，根据树的后续遍历的规律，然后逐个将子节点加入栈
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
stack = [root]
ans = []
while stack:
node = stack.pop()
ans.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ans[::-1]
Recursion
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.ans = []
self.dfs(root)
return self.ans
def dfs(self, root):
if root is None:
return
self.dfs(root.left)
self.dfs(root.right)
self.ans.append(root.val)
