层次遍历

一、层次遍历 二、训练 2.1、637. 二叉树的层平均值

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        if not root:
            return []
        
        ret = []
        que = [root]
        while que:
            queSize = len(que)
            cSum = 0
            for i in range(queSize):
                node = que.pop(0)
                cSum += node.val
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                    
                
            ret.append(cSum/queSize)
        return ret

2.2、107. 二叉树的层次遍历 II

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        que = []
        que.append(root)
        ret = []
        while len(que) > 0:
            queSize = len(que)
            subList = []
            for i in range(queSize):
                cur = que.pop(0)
                if cur:
                    subList.append(cur.val)
                    que.append(cur.left)
                    que.append(cur.right)
            
            if len(subList) > 0:
                ret.append(subList)
        ret.reverse()
        return ret

2.3、102. 二叉树的层次遍历

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        que = [root]
        ret = [[root.val]]
        
        while que:
            queSize = len(que)
            curRet = []
            for i in range(queSize):
                node = que.pop(0)
                if node.left:
                    que.append(node.left)
                    curRet.append(node.left.val)
                if node.right:
                    que.append(node.right)
                    curRet.append(node.right.val)
            if curRet:
                ret.append(curRet)
        return ret

2.4、111. 二叉树的最小深度

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        que = []
        que.append(root)
        level = 0
        while len(que) > 0:
            queSize = len(que)
            for i in range(queSize):
                node = que.pop(0)
                if not node.left and not node.right:
                    return level + 1
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            level += 1
        return level

2.5、429. N叉树的层序遍历

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
        ret = [[root.val]]
        que = [root]
        
        while que:
            queSize = len(que)
            curList = []
            for i in range(queSize):
                node = que.pop(0)
                for n in node.children:
                    if n:
                        curList.append(n.val)
                        que.append(n)
            if curList:
                ret.append(curList)
        return ret

2.6、993. 二叉树的堂兄弟节点

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        
        if not root:
            return False
        
        que = [root]

        while que:
            px = -1
            py = -1
            queSize = len(que)
            for i in range(queSize):
                node = que.pop(0)
                if node.left:
                    que.append(node.left)
                    if node.left.val == x :
                        px = node.val
                    if node.left.val == y:
                        py = node.val
                if node.right:
                    que.append(node.right)
                    if node.right.val == x :
                        px = node.val
                    if node.right.val == y:
                        py = node.val
            if px != -1 and py != -1 and px != py:
                return True
        return False

2.7、103. 二叉树的锯齿形层次遍历 相当于层次遍历，添加一个翻转标志

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        que = [root]
        ret = [[root.val]]
        rflag = False 
        while que:
            queSize = len(que)
            curRet = []
            for i in range(queSize):
                node = que.pop(0)
                if node.left:
                    que.append(node.left)
                    curRet.append(node.left.val)
                if node.right:
                    que.append(node.right)
                    curRet.append(node.right.val)
            if curRet:
                if rflag:
                    ret.append(curRet)
                else:
                    ret.append(curRet[::-1])
                rflag = ~rflag
        return ret