[题型]树-BFS

1. 当前节点值.val
2. 左子节点.left，右子节点.right

BFS

宽度优先搜索，按“层”进行的搜索算法。即迭代法。

适合解决与层数相关的Tree题目。

按层搜索需要保存层的信息，所以需要辅助队列。.left和.right操作留作后续使用。

当辅助队列需要拿值时，使用queue.pop(0)先进先入式取值。

:star:[102]二叉树的层序遍历

给定一个二叉树（默认前序：根-左-右），返回按层序遍历得到的节点值。

:o:广度优先搜索

1. 通过辅助队列，实现该层遍历
2. 将下层节点依次存入辅助队列
3. 考虑无根节点情况

通过辅助队列，实现该层遍历：由于辅助队列是不断维护的，所以只能通过预先计算每层操作次数来限制。

...
res = []
queue = [root]
while queue:  # 当维护的队列不再存有节点时结束
    size = len(queue)  # 必须预先计算本次的遍历次数
    tmp = []
    for _ in range(size):
        r = queue.pop(0)  # 队列前进先出式取值
        tmp.append(r.val)
...

将下层节点依次存入辅助队列：弹出节点并记录值之后应当立即维护队列，将左右子节点存入。

        ...
        if r.left:
            queue.append(r.left)
        if r.right:
            queue.append(r.right)
    res.append(tmp)
return res

考虑无根节点情况：作为特例，需要在最上层进行拦截。

if not root:
    return []
...

:star:[101]对称二叉树

给定一个二叉树，检查它是否镜像对称。

:sweat:广度优先搜索

1. 按层判断是否镜像对称，需要处理好null值问题

按层判断是否镜像对称，需要处理好null值问题：null值导致无法使用.val，.left和.right，所以只能通过判断重新处理。

queue = [root]
while queue:
    tmp = []
    size = len(queue)
    for _ in range(size):
        r = queue.pop(0)
        if r != None:
            tmp.append(r.val)
            if r.left:
                queue.append(r.left)
            else:
                queue.append(None)
            if r.right:
                queue.append(r.right)
            else:
                queue.append(None)
        else:
            tmp.append(None)
    rev = tmp[::-1]
    if rev != tmp:
        return False
return True

:o:广度优先搜索+优化队列存储方式

1. 一次取出两个节点，判断左右镜像对称节点取值是否相同
2. 判断完之后按照由外至内存储这两个节点的子节点
3. 考虑特殊情况

一次取出两个节点，判断左右镜像对称节点取值是否相同：这里左右镜像对称节点是由后续的存储方式决定的。

...
queue = [root.left, root.right]
while queue:
    left = queue.pop(0)
    right = queue.pop(0)
    if not (left or right):  # 一定要理解 not (A or B) 中 or 的妙处，既拦截左右都不存在，也不影响结果
        continue
    if not (left and right):
        return False
    if left.val != right.val:
        return False
    ...

判断完之后按照由外至内存储这两个节点的子节点：由于队列是先进先出，而且取出的时候是成对取出，所以存入的时候是成对存入。

    ...
    queue.append(left.left)
    queue.append(right.right)
    queue.append(left.right)
    queue.append(right.left)
return True

考虑特殊情况：即无根节点，根节点无左右子节点情况。

if not root and not (root.left or root.right):
    return True

:star:[104]二叉树的最大深度

给定一个二叉树，找出其最大深度。

:o:广度优先搜索

1. 设立标志，不断按层遍历二叉树，同时更新标志
2. 考虑特殊情况

设立标志，不断按层遍历二叉树，同时更新标志：正常广度优先搜索。

...
sum = 0
queue = [root]
while queue:
    sum += 1
    size = len(queue)
    for _ in range(size):
        r = queue.pop(0)
        if r.left:
            queue.append(r.left)
        if r.right:
            queue.append(r.right)
    return sum

:star:[226]翻转二叉树

翻转一颗二叉树。

:o:广度优先搜索

要记住，当二叉树父节点交换时，该父节点后续子树会更随父节点变化

1. 逐层按节点交换左右子树
2. 非空子树交由队列留作下次处理
3. 考虑特殊情况

逐层按节点交换左右子树：实际上无需考虑逐层的影响，每个节点都交换子树即可。

queue = [root]
while queue:
    tmp = queue.pop(0)
    tmp.left, tmp.right = tmp.right, tmp.left

非空子树交由队列留作下次处理：这里一定要按照左右顺序存储，实质上左右顺序已由刚才调整完。

    ...
    if tmp.left:
        queue.append(tmp.left)
    if tmp.right:
        queue.append(tmp.right)
return root

考虑特殊情况：当根节点不存在时，返回None即可。

if not root:
    return None

:star:[617]合并二叉树

给定一个二叉树，将他们合并为一个新的二叉树。如果两个节点重复，则将值相加作为合并后的新值。否则不为NULL的节点直接作为新二叉树的节点。

:warning: ​广度优先搜索

由于需要使用collections.deque的特性和重新构造合并后的二叉树，所以这里不做学习。

:star:[199]二叉树的右视图

给定一个二叉树的根节点，返回从右侧所能看到的节点值（每层最后节点值）。

:o:广度优先搜索

1. 逐层判断节点是否为当前层最后一个节点，如果是则返回其值

if not root:
    return []
queue = [root]
res = []
while queue:
    size = len(queue)
    for i in range(size):
        r = queue.pop(0)
        if r.left:
            queue.append(r.left)
        if r.right:
            queue.append(r.right)
        if i == size - 1:
            res.append(r.val)
   return res

:star:[103]二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历（先从左到右，再从右到左，层与层之间交替进行）

1. 构造标志反映是否逆序，对层序遍历进行处理
2. 考虑特殊情况

构造标志反映是否逆序，对层序遍历进行处理：正常的层序遍历+翻转。

...
queue = [root]
res = []
flag = 1
while queue:
    size = len(queue)
    tmp = []
    for _ in range(size):
        r = queue.pop(0)
        tmp.append(r.val)
        if r.left:
            queue.append(r.left)
        if r.right:
            queue.append(r.right)
    if flag == 1:
        res.append(tmp)
    else:
        res.append(tmp[::-1])
    flag *= -1
return res

考虑特殊情况：即无根节点的情况。

if not root:
    return []
...

:star:[111]二叉树的最小深度

给定一个二叉树，找出其最小深度。

1. 通过层序判断二叉树最小深度
2. 考虑特殊情况

通过层序判断二叉树最小深度：最小深度通过层序中最早出现叶子节点判断。

...
queue = [root]
res = 0
while queue:
    res += 1
    size = len(queue)
    for _ in range(size):
        r = queue.pop(0)
        if r.left:
            queue.append(r.left)
        if r.right:
            queue.append(r.right)
        if not r.left and not r.right:
            return res

考虑特殊情况：即无根节点情况。

if not root:
    return 0
...

:star:[429]N叉树的层序遍历

给定一个N叉树，返回其节点值的层序遍历（从左到右，逐层遍历）

1. 确定每层遍历元素个数，如果有子节点则添加至队列
2. 考虑特殊情况

确定每层遍历元素个数，如果有子节点则添加至队列：维护队列和计算该层遍历元素个数很重要（注意子节点为数组，所以用加法扩充入队列）。

...
queue = [root]
res = []
while queue:
    size = len(queue)
    tmp = []
    for _ in range(size):
        r = queue.pop(0)
        tmp.append(r.val)
        if r.children:
            queue += r.children
    res.append(tmp)
return res

考虑特殊情况：即无根节点情况。

if not root:
    return []
...

:star:[515]在每个树行中找最大值

给定一棵二叉树的根节点，找出该二叉树中每一层的最大值。

1. 逐层遍历，寻找最大值
2. 考虑特殊情况

逐层遍历，寻找最大值：注意节点最小取值为$2^{31}$。

...
queue = [root]
res = []
while queue:
    size = len(queue)
    tmp = - 2 ** 31
    for _ in range(size):
        r = queue.pop(0)
        tmp = max(tmp, r.val)
        if r.left:
            queue.append(r.left)
        if r.right:
            queue.append(r.right)
    res.append(tmp)
return res

考虑特殊情况：即无根节点情况。

if not root:
    return []
...