二叉树 | 层序遍历 | leecode刷题笔记

跟随carl代码随想录刷题语言：python👍carl哥太牛了！！！

Begonia_cat

1008人浏览 · 2022-08-10 15:42:14

Begonia_cat · 2022-08-10 15:42:14 发布

文章目录

二叉树的层序遍历——广度优先

跟随carl代码随想录刷题
语言：python
👍carl哥太牛了！！！

二叉树的层序遍历——广度优先

从左到右，一层一层地遍历二叉树。
需要借用队列辅助：

队列先进先出，符合一层一层遍历的逻辑
栈先进后出，适合模拟深度优先遍历的逻辑

102. 二叉树的层序遍历

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

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
👉示例 2：
输入：root = [1]
输出：[[1]]
👉示例 3：
输入：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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:  # 如果当前节点的左节点存在
                    que.append(cur.left)
                if cur.right:  # 如果当前节点的右节点存在
                    que.append(cur.right)
            results.append(result)

        return results

107. 二叉树的层序遍历 II

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

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
👉示例 2：
输入：root = [1]
输出：[[1]]
👉示例 3：
输入：root = []
输出：[]

题目分析

在104的基础上，把results反转一下就行：return results[::-1]

完整代码如下

# 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]]:
        results = []

        if not root:
            return results

        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(result)
        return results[::-1]

199. 二叉树的右视图

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

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
👉示例 2:
输入: [1,null,3]
输出: [1,3]
👉示例 3:
输入: []
输出: []

题目分析

在104的基础上，加一条判断：如果当前值是该行最后面的元素，那就放进results数组中。

完整代码如下

# 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]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            
            # 写法2：可以直接在这里取`que`的最后一个值
            # results.append(que[-1].val)
            
            for i in range(size):  
                cur = que.popleft()  
                if i == size-1:  # 新代码
                    results.append(cur.val)  # 新代码
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
        return results

637. 二叉树的层平均值

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

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

题目分析

遍历的时候，每层求一个总和，再取平均值。

完整代码如下

# 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]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)

			# 求和、取平均
            sum = 0
            for i in result:
                sum += i
            results.append(sum/len(result))
            
        return results

求和取平均也可以直接写在for i in range(size):中：

# 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]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            sum_ = 0  # 新代码
            for _ in range(size):
                cur = que.popleft()
                sum_ += cur.val  # 新代码
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(sum_/size)  # 新代码
              
        return results

429. N 叉树的层序遍历

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

题目分析

在104的基础上修改：

节点有多个孩子if cur.children: result.extend(children)
python之append、expend函数详解
- append是把内容原封不动追加到列表末尾
  - A = [1, 2]
  - B = [3, 4, 5]
  - A.append(B)
  - A = [1, 2, [3, 4, 5]]
- extend是把列表拆开，追加到列表末尾。代码示范：
  - A = [1, 2]
  - B = [3, 4, 5]
  - A.extend(B)
  - A = [1, 2, 3, 4, 5]

完整代码如下

"""
# 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: 'Node') -> List[List[int]]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.children:
                    que.extend(cur.children)  # 新代码
            results.append(result)
            
        return results

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

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

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

题目分析

在104的基础上进行修改：层序遍历，取最大值。

完整代码如下

# 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]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []

            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
                    
            # 取每层最大值        
            max_ = result[0]
            for i in result:
                if i > max_:
                    max_ = i
            results.append(max_)

			# 上述`取每层最大值`的代码，可以直接用`max()`一行代码实现
			# results.append(max(result))
            
        return results

116. `中等`填充每个节点的下一个右侧节点指针

题目：给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，‘#’ 标志着每一层的结束。
👉示例 2:
输入：root = []
输出：[]

题目分析

在单层遍历的时候，记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了。

完整代码如下

"""
# 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 None
            
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            for i in range(size):
                cur = que.popleft()
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
                if i == size-1:  # 每层最后一个节点指向none，等于默认值，不用做修改
                    break
                cur.next = que[0]  # 指向该层前一个节点
        return root

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

题目：给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

题目分析

和116题意一样，代码一模一样

104. 二叉树的最大深度

题目：给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

题目分析

返回结果集的长度

if not root: return 0
return len(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 maxDepth(self, root: Optional[TreeNode]) -> int:
        results = []
        if not root:
            return 0
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:  # 如果当前节点的左节点存在
                    que.append(cur.left)
                if cur.right:  # 如果当前节点的右节点存在
                    que.append(cur.right)
            results.append(result)

        return len(results)

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:
        results = []
        if not root:
            return 0
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                
                if cur.left:  # 如果当前节点的左节点存在
                    que.append(cur.left)
                if cur.right:  # 如果当前节点的右节点存在
                    que.append(cur.right)
                if cur.left == None and cur.right == None:
                    break  # 出现了没有左右孩子的节点，就终止循环
            
            results.append(result)  # 记录结果集
            if cur.left == None and cur.right == None:
                break # 终止while循环        

        return len(results)

carl的code：

# 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 root == None:
            return 0

        #根节点的深度为1
        queue_ = [(root,1)]
        while queue_:
            cur, depth = queue_.pop(0)
            
            if cur.left == None and cur.right == None:
                return depth
            #先左子节点，由于左子节点没有孩子，则就是这一层了
            if cur.left:
                queue_.append((cur.left,depth + 1))
            if cur.right:
                queue_.append((cur.right,depth + 1))

        return 0

559. `简单`N 叉树的最大深度

题目：给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

题目分析

if cur.children: que.extend(cur.children)
返回return len(result)

完整代码如下

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

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        results = []

        if not root:
            return 0

        from collections import deque
        que = deque([root])

        while(que):
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.children:
                    que.extend(cur.children)
                
            results.append(result)

        return len(results)

222. 完全二叉树的节点个数

题目：给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
👉示例1：

输入：root = [1,2,3,4,5,6]
输出：6
👉示例 2：
输入：root = []
输出：0
👉示例 3：
输入：root = [1]
输出：1

题目分析

层序遍历，结果全部放入result中，输出len(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 countNodes(self, root: Optional[TreeNode]) -> int:
        result = []
        
        if not root:
            return 0
            
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)

        return len(result)

404. 左叶子之和

题目：给定二叉树的根节点 root ，返回所有左叶子之和。

题目分析

本题统计的是左叶子而不是每层的左端点喔
所以，需要加一个判断条件：

如果当前节点cur的左节点存在，
并且左节点的左孩子和左节点的右孩子都不存在
则cur.left是左节点，可以加入结果集result += cur.left.val

完整代码如下

# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        result = 0

        if not root:
            return 0

        que = deque([root])

        while que:
            cur = que.popleft()
            # size = len(que)
            # for _ in size:

            if cur.left and not cur.left.left and not cur.left.right:
                result += cur.left.val
            if cur.left:
                que.append(cur.left)
            if cur.right:
                que.append(cur.right)
        return result

513. 找树左下角的值

题目：给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

题目分析

输出最后一层的第一个值return result[-1][0]

完整代码如下

# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        results = []
        if not root:
            return None
        
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(result)
        return results[-1][0]

在上述代码中修改一下，队列可以做的，栈也可以，毕竟这个题不讲究顺序嘛

# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        result = 0

        if not root:
            return 0

        stack = []
        stack.append(root)

        while stack:
            cur = stack.pop()

            if cur.left and not cur.left.left and not cur.left.right:
                result += cur.left.val
            if cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)
        return result

CSDN学习社区

CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！

更多推荐

嵌入式作业（七）：基于Ardunio的STM32串口通信

嵌入式作业（七）0作业要求1Ardunio 完成STM32的串口通信（1）安装Ardunio IDE（2）stm32串口通信2关于 stduino IDE0作业要求安装 Ardunio IDE 和相关软件支持库，在Ardunio 完成STM32板子的串口通信程序：（1）持续向串口输出“Hello world！”；（2）当接收到“stop!”时，停止输出。网上有一个国人版的MCU集成开发平台， st

CSDN学习社区

JDBC详解

JDBC文章目录JDBC什么是JDBC?JDBC驱动程序:Java使用JDBC访问数据库的步骤:设置classpath:Oracle连接字符串的书写格式:简单的例子:常用数据库的驱动程序及JDBC URL:Oracle数据库:SQL Server数据库MySQL数据库Access数据库PreparedStatement接口:JNDI-数据源（Data Source）与连接池（Connection

CSDN学习社区

“模式识别与机器学习”学习笔记no2.再谈感知机

接**上篇：上篇主要进行了PLA，Pocket算法的理论过程分析和在给定数据集上利用pocket算法对数据集进行分类学习，得到错分数量最少的分类面。上篇中pocket算法的过程已经进行了编程和测试，框架已经建立了起来，这一篇主要上篇中没有提到或涉及不深的几个问题。1.数据集的构造。上篇是直接使用了题目给的向量，这次来根据正态分布来产生数据集。np.random.normal函数可以根据均值和方差生

CSDN学习社区

所有评论(0)

查看更多评论

Begonia_cat

@qq_44250700

已为社区贡献6条内容

二叉树 | 层序遍历 | leecode刷题笔记

Begonia_cat

文章目录

二叉树的层序遍历——广度优先

102. 二叉树的层序遍历

题目分析

完整代码如下

107. 二叉树的层序遍历 II

题目分析

完整代码如下

199. 二叉树的右视图

题目分析

完整代码如下

637. 二叉树的层平均值

题目分析

完整代码如下

429. N 叉树的层序遍历

题目分析

完整代码如下

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

题目分析

完整代码如下

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

题目分析

完整代码如下

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

题目分析

104. 二叉树的最大深度

题目分析

完整代码如下

111. 二叉树的最小深度

题目分析

完整代码如下

559. 简单N 叉树的最大深度

题目分析

完整代码如下

222. 完全二叉树的节点个数

题目分析

完整代码如下

404. 左叶子之和

题目分析

完整代码如下

513. 找树左下角的值

题目分析

完整代码如下

在上述代码中修改一下，队列可以做的，栈也可以，毕竟这个题不讲究顺序嘛

所有评论(0)

Begonia_cat

116. `中等`填充每个节点的下一个右侧节点指针

559. `简单`N 叉树的最大深度