-
Notifications
You must be signed in to change notification settings - Fork 0
/
102_binary-tree-level-order-traversal.py
66 lines (60 loc) · 1.75 KB
/
102_binary-tree-level-order-traversal.py
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
60
61
62
63
64
65
66
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#@author: rye
#@time: 2019/3/30
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
'''
非递归
考研的时候复习数据结构对这个很有印象,不过现在确实忘了。参考链接:https://blog.csdn.net/yurenguowang/article/details/76906620
看了参考链接才想起来。
'''
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
if not root:
return res
queue = []
queue.append(root)
while len(queue) != 0:
tmp = []
for i in range(len(queue)):
r = queue.pop(0)
if r.left:
queue.append(r.left)
if r.right:
queue.append(r.right)
tmp.append(r.val)
res.append(tmp)
return res
# 也可以考虑递归(个人不太喜欢用递归)
'''
因为res的下标被控制了,所以只需要用dfs搜索到所有节点,控制到对应下标就行。
'''
class Solution1:
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
def dfs(node, level, res):
if not node:
return
if len(res) < level:
res.append([])
res[level - 1].append(node.val)
dfs(node.left, level + 1, res)
dfs(node.right, level + 1, res)
res = []
dfs(root, 1, res)
return res
if __name__ == '__main__':
pass