Given a binary tree, return the preorder traversal of its nodes' values.
For example:
- Given binary tree {1,#,2,3},
1
2
/
3
- return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
Python Solution 1:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root: return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return res
Python Solution 2:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
def preorder(root, res):
if not root: return
res.append(root.val)
preorder(root.left, res)
preorder(root.right, res)
res = []
preorder(root, res)
return res
Summary:
- stack
LeetCode: 144. Binary Tree Preorder Traversal
近期评论