Coding

代码随想录算法训练营Day15 | 二叉树层序遍历、LeetCode226 翻转二叉树、LeetCode101 对称二叉树

Posted by 慕念 on March 6, 2024

层序遍历

题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

层序遍历刷题：

LeetCode102 二叉树的层序遍历

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：

102二叉树的层序遍历

❗如何判断同一层的节点：记录队列的长度size，代表二叉树这一层有几个元素

  • 6进入队列，size=1，弹出1个元素6
  • 将6的左孩子4和右孩子7加入队列，size=2
    • 弹出元素4，将4的左右孩子加入
    • 弹出元素7，将7的左右孩子加入，size=4（表示第三层有4个节点）
# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        que = deque()
        if not root:
            return
        
        res = []
        que.append(root)
        while que:
            length = len(que)
            level = []
            for i in range(length):
                node = que.popleft()
                level.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(level)
        return res

LeetCode107 二叉树的层次遍历II

✌把res数组反转即可

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        que = deque()
        if not root:
            return
        
        res = []
        que.append(root)
        while que:
            length = len(que)
            level = []
            for i in range(length):
                node = que.popleft()
                level.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(level)
        return res[::-1]	# 反转

LeetCode199 二叉树的右视图

✌判断是不是每层最后一个元素，如果是则加入res

不是双重列表，所以不需要level=[]

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        que = deque()
        if not root:
            return
        
        res = []
        que.append(root)
        while que:
            length = len(que)
            for i in range(length):
                node = que.popleft()
                if i == length - 1:	# 判断是否是每层最后一个元素
                    
                    res.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return res

LeetCode637 二叉树的层平均值

✌获得列表后求平均

class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        que = deque()
        if not root:
            return
        
        res = []
        que.append(root)
        while que:
            length = len(que)
            level = []
            for i in range(length):
                node = que.popleft()
                level.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(level)
        
        final_res=[]
        for sublist in res:
            final_res.append(sum(sublist)/float(len(sublist)))
        return final_res

或者直接每层求平均

LeetCode429 N叉树的层序遍历

✌node.children是用list存储

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        que = deque()
        if not root:
            return
        
        res = []
        que.append(root)
        while que:
            length = len(que)
            level = []
            for i in range(length):
                node = que.popleft()
                level.append(node.val)
                for child in node.children:
                    que.append(child)
            res.append(level)     
        return res

LeetCode515 在每个树行中找最大值

✌在每一层比较大小

class Solution(object):
    def largestValues(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        que = deque()
        if not root:
            return
        
        res = []
        que.append(root)
        while que:
            max_val = float('-inf')
            for i in range(len(que)):
                node = que.popleft()
                if node.val > max_val:
                    max_val = node.val
                # 或者写成max_val = max(max_val, node.val)
                
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(max_val)
        return res

LeetCode116 填充每个节点的下一个右侧节点指针

❗本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        que = deque()
        if not root:
            return
        
        que.append(root)
        while que:
            length = len(que)
            prev = None # 记录前一个节点
            for i in range(length):
                node = que.popleft()
                if prev:
                    prev.next = node
                prev = node

                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return root

LeetCode117 填充每个节点的下一个右侧节点指针II

同上一题116，这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑

LeetCode104 二叉树的最大深度

✌每层level++

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        que = deque()
        if not root:
            return 0
        
        level = 0
        que.append(root)
        while que:
            length = len(que)
            level += 1
            for i in range(length):
                node = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return level

LeetCode111 二叉树的最小深度

❗只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        que = deque()
        if not root:
            return 0
        
        depth = 0
        que.append(root)
        while que:
            length = len(que)
            depth += 1	# 记录最小深度
            for i in range(length):
                node = que.popleft()
                if not node.left and not node.right:	# 当左右孩子都为空的时候，说明是最低点的一层了，退出
                
                    return depth
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return depth
CATALOG
    FEATURED TAGS
    安全攻防综合实验 OS 信息系统安全 SeedLab watermark Coding