迭代：广度优先遍历，递归：深度优先遍历
题目
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
题解
方法一：迭代，广度优先变遍历
- 算法与思路分析
采用队列（FIFO），每层入队，统计该层结点数，每层出队完时，下一层入队。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
from queue import Queue
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def create_tree(list_tree):
if not list_tree:
return []
new_queue= Queue()
root = TreeNode(list_tree[0])
new_queue.put(root)
count = 1
while not new_queue.empty() and count<len(list_tree):
dequeue = new_queue.get()
if not dequeue.left and not dequeue.right:
if count<len(list_tree) and list_tree[count]:
dequeue.left=TreeNode(list_tree[count])
count= count+1
if count<len(list_tree) and list_tree[count]:
dequeue.right=TreeNode(list_tree[count])
count= count+1
if dequeue.left:
new_queue.put(dequeue.left)
if dequeue.right:
new_queue.put(dequeue.right)
return root
class Solution:
def levelOrder(self, root: TreeNode):
if not root:
return None
new_queue=Queue()
list_level=[]
new_queue.put(root)
while not new_queue.empty():
count =new_queue.qsize()
tmp=[]
while count:
dequeue= new_queue.get()
tmp.append(dequeue.val)
if dequeue.left:
new_queue.put(dequeue.left)
if dequeue.right:
new_queue.put(dequeue.right)
count= count-1
list_level.append(tmp)
return list_level
root = [3,9,20,None,None,15,7]
root_tree=create_tree(root)
a=Solution()
result =a.levelOrder(root_tree)
result
|
[[3], [9, 20], [15, 7]]
时间复杂度： O(n)
空间复杂度：O(n)
方法二：递归，深度优先遍历
广度优先处理切割很明显，如图按每层进行切割
深度优先处理时，先调整二叉树形态，如下，田字型每一行为每一层对应结点
按照深度优先的处理顺序，会先访问节点 1，再访问节点 2，接着是节点 3。
之后是第二列的 4 和 5，最后是第三列的 6。
每次递归的时候都需要带一个 index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的 list 不存在，就加入一个空 list 进去。
动态演示如下:
时间复杂度：O(N)
空间复杂度：O(h)，h 是树的高度
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
| class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
res = []
def dfs(index,r):
if len(res)<index:
res.append([])
res[index-1].append(r.val)
if r.left:
dfs(index+1,r.left)
if r.right:
dfs(index+1,r.right)
dfs(1,root)
return res
root = [3,9,20,None,None,15,7]
root_tree=create_tree(root)
a=Solution()
result =a.levelOrder(root_tree)
result
|
[[3], [9, 20], [15, 7]]
