给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| 示例: 二叉树:[3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7 返回其层次遍历结果:
[ [3], [9,20], [15,7] ]
|
代码及解析:
将同一层的节点存到一个临时数组中,访问完同一层的所有节点,就将该临时数组添加到结果res数组中,利用队列每访问一个节点,将其pop掉,然后将该节点的左右节点推入队列,直到队列为空,返回结果res结束。
代码:
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 Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] res=[] deque=[root] while deque: tmp = [] node = [] while deque: que=deque.pop(0) tmp.append(que.val) if que.left: node.append(que.left) if que.right: node.append(que.right) deque.extend(node) res.append(tmp) return res
|
注释:
1 2 3 4 5
| extend与append的区别: 两者作用差不多,都是添加元素至数组中,两者区别在于,比如添加一个数组,前者是按顺序在数组最后一个一个的添加进去,而后者是直接将整个数组添加进去, 比如:a=[1],b=[2,3] extend:a=[1,2,3] append:a=[1,[2,3]]
|
举一反三:
leetcode-107:与上述题目一样,只是将结果反向输出即可
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution: def levelOrderBottom(self, root: TreeNode) -> List[List[int]]: if not root: return [] deque=[root] res=[] while deque: temp=[] extend=[] while deque: que=deque.pop(0) temp.append(que.val) if que.left: extend.append(que.left) if que.right: extend.append(que.right) deque.extend(extend) res.append(temp) return res[::-1]
|
leetcode-104:求二叉树的最大深度,利用层序遍历,每遍历一层深度+1
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution: def maxDepth(self, root: TreeNode) -> int: max=0 if not root: return 0 deque=[root] while deque: tmp = [] node = [] while deque: que=deque.pop(0) tmp.append(que.val) if que.left: node.append(que.left) if que.right: node.append(que.right) if tmp: max+=1 deque.extend(node)
return max
|
写在最后:
如果您有任何不明白,或描述上述有问题,请在下方留言。