代码随想录算法训练营第十三天|层序遍历10，226.翻转二叉树，101.对称二叉树

系列文章目录

代码随想录算法训练营第一天|数组理论基础，704. 二分查找，27. 移除元素
代码随想录算法训练营第二天|977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II
代码随想录算法训练营第三天|链表理论基础，203.移除链表元素，707.设计链表，206.反转链表
代码随想录算法训练营第四天|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，总结
代码随想录算法训练营第五天|哈希表理论基础，242.有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和
代码随想录算法训练营第六天|454.四数相加II，383. 赎金信，15. 三数之和，18. 四数之和，总结
代码随想录算法训练营第七天|344.反转字符串，541. 反转字符串II，卡码网：54.替换数字，151.翻转字符串里的单词，卡码网：55.右旋转字符串
代码随想录算法训练营第八天|28. 实现 strStr()，459.重复的子字符串，字符串总结，双指针回顾
代码随想录算法训练营第九天|理论基础，232.用栈实现队列，225. 用队列实现栈
代码随想录算法训练营第十天|20. 有效的括号，1047. 删除字符串中的所有相邻重复项，150. 逆波兰表达式求值
代码随想录算法训练营第十一天|239. 滑动窗口最大值，347.前 K 个高频元素，总结
代码随想录算法训练营第十二天|理论基础，递归遍历，迭代遍历，统一迭代

---

图论里的深搜和广搜其实对应的就是二叉树的递归和层序遍历

层序遍历10道题

视频讲解：讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode：102.二叉树的层序遍历
对应题目： 102.二叉树的层序遍历；107.二叉树的层次遍历II；199.二叉树的右视图；637.二叉树的层平均值；429.N叉树的层序遍历；515.在每个树行中找最大值；116.填充每个节点的下一个右侧节点指针；117.填充每个节点的下一个右侧节点指针II；104.二叉树的最大深度；111.二叉树的最小深度

核心思想：层序遍历一个二叉树就是从左到右一层一层的去遍历二叉树，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过现在是应用在二叉树上。

---

102.二叉树的层序遍历：

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

• python中deque是类似 list 的容器，两端都能实现快速 append 和 pop (双端队列)
• 两层循环：一层用于遍历整个二叉树，在遍历整个二叉树的内部增加另一层循环用于遍历二叉树的每一层元素。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result=[]
        queue=collections.deque([root])
        while queue:
            level=[]#遍历每一层元素之前设立一个数组，用于保存每一层的元素
            for _ in range(len(queue)):
                cur=queue.popleft()#弹出队列元素 
                level.append(cur.val)#将弹出的元素加入这一层的数组中
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            result.append(level)
        return result

107. 二叉树的层序遍历 II：

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

• 思路与层序遍历的思路一致，只要将层序遍历返回的数组进行翻转即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue=collections.deque([root])
        result=[]
        while queue:
            level=[]
            for _ in range(len(queue)):
                cur=queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            result.append(level)
        return result[::-1]

199. 二叉树的右视图：

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

• 思路与层序遍历的思路一致，只要在层序遍历的每一层遍历的结果中获取数组的最后一个元素即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        queue=collections.deque([root])
        result=[]
        while queue:
            level=[]
            for _ in range(len(queue)):
                cur=queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            result.append(level[-1])
        return result

637.二叉树的层平均值：

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

• 层序遍历的每一层遍历的结果取平均值后加入最终的result数组即可

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        queue=collections.deque([root])
        result=[]
        while queue:
            level=[]
            level_sum=0
            for _ in range(len(queue)):
                cur=queue.popleft()
                level.append(cur.val)
                level_sum+=cur.val
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            avg=level_sum/len(level)
            result.append(avg)
        return result

429.N叉树的层序遍历：

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

• N叉树的一个节点有多个孩子，因此需要增加一个for循环，遍历加入一个节点的孩子。

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result=[]
        queue=collections.deque([root])
        while queue:
            level=[]#遍历每一层元素之前设立一个数组，用于保存每一层的元素
            for _ in range(len(queue)):
                cur=queue.popleft()#弹出队列元素 
                level.append(cur.val)#将弹出的元素加入这一层的数组中
                for child in cur.children:
                    queue.append(child)
            result.append(level)
        return result

515. 在每个树行中找最大值：

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

• 在进行层序遍历的每一层遍历时，将得到的结果与当前最大值进行比较之后获得的最大值加入result数组即可

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result=[]
        queue=collections.deque([root])
        while queue:
            level=[]#遍历每一层元素之前设立一个数组，用于保存每一层的元素
            max_val=float('-inf')
            for _ in range(len(queue)):
                cur=queue.popleft()#弹出队列元素 
                max_val=max(max_val,cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            result.append(max_val)
        return result

116. 填充每个节点的下一个右侧节点指针：

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。

• 依旧是对二叉树进行层序遍历，在进行每一层遍历时，增加一个prev节点，用于设置next指针。

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root
        queue=collections.deque([root])
        while queue:
            level=[]#遍历每一层元素之前设立一个数组，用于保存每一层的元素
            prev=None
            for _ in range(len(queue)):
                cur=queue.popleft()#弹出队列元素 
                if prev:
                    prev.next=cur
                prev=cur
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return root

117. 填充每个节点的下一个右侧节点指针 II：

给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。初始状态下，所有 next 指针都被设置为 NULL 。

• 和上一题的思路及代码一模一样

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        queue=collections.deque([root])
        while queue:
            prev=None
            for _ in range(len(queue)):
                cur=queue.popleft()#弹出队列元素 
                if prev:
                    prev.next=cur
                prev=cur
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return root

104.二叉树的最大深度：

给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

• 按照层序遍历的循环进行计数，每针对一层进行循环就加一。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        level=0
        queue=collections.deque([root])
        while queue:
            level+=1
            for _ in range(len(queue)):
                cur=queue.popleft()#弹出队列元素 
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return level

111. 二叉树的最小深度：

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

• 按照层序遍历的循环进行计数，每针对一层进行循环就加一，如果出现有节点左孩子和右孩子都不存在的情况，就提前结束循环返回当前层数。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        level=0
        queue=collections.deque([root])
        while queue:
            level+=1
            for _ in range(len(queue)):
                cur=queue.popleft()#弹出队列元素 
                if not cur.left and not cur.right:
                    return level
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return level

226.翻转二叉树

题目链接： 226.翻转二叉树
题目内容： 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
视频讲解： 听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树

层序遍历方法：

• 在层序遍历的过程中，调换左右孩子节点即可

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        queue=collections.deque([root])
        while queue:
            for _ in range(len(queue)):
                cur=queue.popleft()#弹出队列元素 
                if cur.left or cur.right:
                    cur.left,cur.right=cur.right,cur.left
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return root

递归法（前序遍历）：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

迭代法（前序遍历）：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None      
        stack = [root]        
        while stack:
            node = stack.pop()   
            node.left, node.right = node.right, node.left                   
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)  
        return root

递归法（中序遍历）：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        self.invertTree(root.left)
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        return root

迭代法（中序遍历）：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None      
        stack = [root]        
        while stack:
            node = stack.pop()                   
            if node.left:
                stack.append(node.left)
            node.left, node.right = node.right, node.left               
            if node.left:
                stack.append(node.left)       
        return root

递归法（后序遍历）：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

迭代法（后序遍历）：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None      
        stack = [root]        
        while stack:
            node = stack.pop()                   
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)  
            node.left, node.right = node.right, node.left               
     
        return root

101.对称二叉树

题目链接： 101.对称二叉树
题目内容： 给你一个二叉树的根节点 root ， 检查它是否轴对称。
视频讲解： 新学期要从学习二叉树开始！ | LeetCode：101. 对称二叉树

递归法：
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，具体比较的是两个子树的里侧和外侧的元素是否相等。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.compare(root.left,root.right)
    def compare(self,left,right):
        if left==None and right!=None:
            return False
        elif left!=None and right==None:
            return False
        elif left==None and right==None:
            return True
        elif left.val!=right.val:
            return False
        outside=self.compare(left.left,right.right)
        inside=self.compare(left.right,right.left)
        isSame=outside and inside
        return isSame