BFS层次遍历的模板

层次遍历模板如下

from collections import deque
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def levelOrder(root: TreeNode) :
    queue = deque()
    if root:
        queue.append(root)
    while queue:
        ##每次for循环是一层
        for _ in range(0, len(queue)):
            root = queue.popleft(0)
            if root:
                queue.append(root.left)
                queue.append(root.right) 

答案

先运行工具类,可以从字符串里生成测试用例

from typing import List
import json
from collections import deque
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def genTreeFromStr(listStr: str):
    list = json.loads(listStr)
    if not list:
        return None
    queue = []
    root = TreeNode(list.pop(0))
    queue.append(root)
    t, i = None, 0
    while queue:
        if(i >= len(list)):
            break
        for _ in range(0, len(queue)):
            t = queue.pop(0)
            if t:
                t.left = None if not list[i] else TreeNode(list[i])
                i += 1
                if(i >= len(list)):
                    break
                t.right = None if not list[i] else TreeNode(list[i])
                i += 1
                queue.append(t.left)
                queue.append(t.right)

    return root


def visitTree(root: TreeNode):
    queue = []
    res = []
    queue.append(root)
    while(len(queue) != 0):
        t = queue.pop(0)
        res.append('null' if(t == None) else t.val)
        if(t):
            queue.append(t.left)
            queue.append(t.right)

    for i in range(len(res)-1, -1, -1):
        if(res[i] == 'null'):
            res.pop(i)
        else:
            break
    print(res)

题目

'''
SO32
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
层次遍历的话 每次对队列做一个类似快照的操作标记这次遍历是一个层次 for _ in range(0, len(queue)):
之后入队的就是新的一层了
'''
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        queue = []
        if root:
            queue.append(root)
        while queue:
            tmp = []
            for _ in range(0, len(queue)):
                root = queue.pop(0)
                if root:
                    tmp.append(root.val)
                    queue.append(root.left)
                    queue.append(root.right)
            if tmp:
                res.append(tmp)
        return res




print(Solution().levelOrder(genTreeFromStr("[3,9,20,null,null,15,7]")))

'''
S107
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
SO32 一个题目只是对输出结果进行了反转操作
'''
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        res = []
        queue = deque()
        if root:
            queue.append(root)
        while queue:
            tmp = []
            for _ in range(0, len(queue)):
                root = queue.popleft()
                if root:
                    tmp.append(root.val)
                    queue.append(root.left)
                    queue.append(root.right)
            if tmp:
                res.append(tmp)
        res.reverse()
        return res 

'''
S111
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/
做一个层次计数
当一个节点没有左右子节点时返回该计数
'''
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        queue = deque()
        if root:
            queue.append(root)
        res = 0
        while queue:
            res += 1
            for _ in range(0, len(queue)):
                root = queue.popleft()
                if root:

                    if not root.left and not root.right:
                        return res
                    queue.append(root.left)
                    queue.append(root.right)
        return res

'''
S559
https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
忽略深度优先遍历
BFS的话思路很简单,做一个层次遍历就OK了
利用元组来记录当前node节点的深度,每次有Children的时候深度+1
dep就是所有深度里的最大深度
'''

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children


class Solution:
    def maxDepth(self, root: 'Node') -> int:
        queue = deque()
        if root:
            queue.append((1, root))
        dep = 0

        while len(queue) != 0:
            currentDep, treeNode = queue.popleft()
            if treeNode:
                dep = max(currentDep, dep)
                for t in [] if not treeNode.children else treeNode.children:
                    queue.append((currentDep+1, t))
        return dep 

'''
S690
https://leetcode-cn.com/problems/employee-importance/submissions/
其实是一棵多叉树的层次遍历
唯一不同的是树的子儿子不是树本身 而是id
用一个dic把每个id和对应的树存起来就解决了
'''




class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates


class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        dic = {}
        for e in employees:
            dic[e.id] = e
        if id not in dic:
            return 0
        root = dic[id]
        res = 0
        queue = deque()
        queue.append(root)
        while queue:
            for _ in range(0, len(queue)):
                root = queue.popleft()
                if root:
                    res += root.importance
                    if root.subordinates:
                        for sub in root.subordinates:
                            queue.append(sub)
        return res 

'''
S933
https://leetcode-cn.com/problems/cousins-in-binary-tree/
层次遍历 并且保存父节点信息
当某层出现x 或y时直接比对 x y是否都有父节点 并且不相等(没有父节点表示他不在这一层次)
'''



class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        queue = deque()
        if root:
            queue.append((root, None))
        parentX = None
        parentY = None

        while queue:
            for _ in range(0, len(queue)):
                root, parent = queue.popleft()
                if root:
                    if root.val == x:
                        parentX = parent
                    if root.val == y:
                        parentY = parent
                    queue.append((root.left, root.val))
                    queue.append((root.right, root.val))
            if parentX != None or parentY != None:
                if not parentX or not parentY:
                    return False
                return parentX != parentY

        return False



print(Solution().isCousins(genTreeFromStr("[1,2,3,null,4,null,5]"), 5, 4))
print(Solution().isCousins(genTreeFromStr("[1,2,3,4]"), 3, 4)) 

'''
[面试题 04.03. 特定深度节点链表](https://leetcode-cn.com/problems/list-of-depth-lcci/)
'''
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
        queue = deque()
        res=[]
        if tree:
            queue.append(tree)
        while queue:
            listNode=ListNode(0)
            tmp=listNode
            for _ in range(0,len(queue)):
                root=queue.popleft()
                if root:
                    tmp.next=ListNode(root.val)
                    tmp=tmp.next
                    queue.append(root.left)
                    queue.append(root.right)
            if listNode.next:
                res.append(listNode.next)
        return res

本文地址：https://blog.csdn.net/qq_21078159/article/details/107100222