102. 二叉树的层序遍历
image-20201204145536430
树之我见
二叉树挺有意思，希望大家都能掌握。我也在为此努力！
其实树用的还是挺多的，比如我在比较2个json的差异的时候，就涉及到遍历树，如果不知道怎么去正确遍历树，还是比较麻烦的。
还有一个应用的地方就是antd的tree，当你要用到这种组件的时候，涉及到大量的递归，用到tree的时候还是蛮多乐趣的。
思路
树的遍历大体上有2种，深度和广度，题目中很明显要求是广度优先遍历。
其实我发现一个规律，如果是按广度，那么用迭代比递归方便，如果是按照深度优先遍历，那么递归比迭代方便。
所以这里我们采取迭代的方式，一层一层把树扒光！
首先我们处于树的顶层，那么我们一层一层去把数据放到队列里面，按照先进先出的规则，处理完毕即可。但是我们这一层要扒光多少个节点，那么我们需要在上一层将其记录。
比如图中的例子，我们先把3放入队列，然后开始判断队列是否为空，队列不是空的话，就按队列的长度N拿出N个元素，并把他们的left和right再放入队列。
队列情况:
1. [3]
2. [9 20] (出来1个元素 3出队列)
3. [15 7] (出来2个元素，9和20，由于9没有left和right，所以只进入15和7)
4. []
出列的元素个数等于队列当前元素个数
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
nodes = [root]
result = []
while len(nodes) > 0:
# 这一层的节点个数
size = len(nodes)
# 先加入空数组
result.append([])
for i in range(size):
# 出队列，并加入到result
current = nodes.pop(0)
result[len(result)-1].append(current.val)
# 如果左/右孩子不为空，则加入队列
if current.left is not None:
nodes.append(current.left)
if current.right is not None:
nodes.append(current.right)
return result
image-20201204150937372
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
result := make([][]int, 0)
deque := []*TreeNode{root}
for len(deque) > 0 {
size := len(deque)
result = append(result, make([]int, 0))
for i:=0; i<size; i++ {
current := deque[0]
result[len(result)-1] = append(result[len(result)-1], current.Val)
if current.Left != nil {
deque = append(deque, current.Left)
}
if current.Right != nil {
deque = append(deque, current.Right)
}
deque = deque[1:]
}
}
return result
}
image-20201204151608520
