描述
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?
分析
简单题，二叉树的先序遍历。当使用迭代方法时，注意入栈的顺序，需要先push右节点，再push左节点。
还有一种不常用的方法Morris遍历，可以做到空间O(1)，时间O(n)。
代码
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def preorderTraversalR(self, root, rs):
if not root:
return
rs.append(root.val)
self.preorderTraversalR(root.left, rs)
self.preorderTraversalR(root.right, rs)
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
rs = []
self.preorderTraversalR(root, rs)
return rs
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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]
"""
rs = []
ss = []
if root:
ss.append(root)
while ss:
cur = ss.pop()
rs.append(cur.val)
if cur.right:
ss.append(cur.right)
if cur.left:
ss.append(cur.left)
return rs
|
Morris
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
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]
"""
rs = []
cur = root
while cur:
if not cur.left:
rs.append(cur.val)
cur = cur.right
else:
node = cur.left
while node.right and node.right != cur:
node = node.right
if not node.right:
rs.append(cur.val)
node.right = cur
cur = cur.left
else:
node.right = None
cur = cur.right
return rs
|