跟随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
Logo

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

更多推荐