144. Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
First
1 Stack
根据栈后进先出的原则,先将右节点放入栈中,然后将左节点放入栈中,这样永远先出来
左节点,然后出来右节点。
class Solution(object):
def preorderTraversal(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.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans
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.ans.append(root.val)
self.dfs(root.left)
self.dfs(root.right)
网友评论