• LeetCode Cookbook 树（2）

    CSDN话题挑战赛第2期
    参赛话题：算法题解

    LeetCode Cookbook 树（2）

       树 的第二部分内容，仍然比较基础！

    637. 二叉树的层平均值（model-I 扩展）

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

    例如：
    在这里插入图片描述

    输入：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]:
        # 层序遍历
        if root is None: return []
        q = collections.deque([root])
        ans = list()
        while q:
            lay,layer = list(),list()
            for node in q:
                layer.append(node.val)
                if node.left: lay.append(node.left)
                if node.right: lay.append(node.right)
            q  = lay
            ans.append(sum(layer)/len(layer))
        return ans

    515. 在每个树行中找最大值（model-I 扩展）

    题目链接：515. 在每个树行中找最大值
    题目大意：给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

    例如：
    在这里插入图片描述

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

    解题思路：层序 拓展题。

    # 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 root is None: return []
        ans = []
        q = [root]
        while q:
            maxVal = -inf
            tmp = q
            q = []
            for node in tmp:
                maxVal = max(maxVal,node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(maxVal)
        return ans

    1302. 层数最深叶子节点的和（model-I 扩展）

    题目链接：1302. 层数最深叶子节点的和
    题目大意：给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。

    例如：
    在这里插入图片描述

    输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出：15

    解题思路： 层序 扩展题目。

    # 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 deepestLeavesSum(self, root: Optional[TreeNode]) -> int: 
        
        # BFS
        q = deque([root])
        while q:
            ans = 0
            for _ in range(len(q)):
                node = q.popleft()
                ans += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return  ans        
        ''''''

    199. 二叉树的右视图（model-I 扩展）

    题目链接：199. 二叉树的右视图
    题目大意：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

    例如：
    在这里插入图片描述

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

    解题思路： 层序 拓展题目。

    # 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 root is None: return []
        q = collections.deque([root])
        ans = list()

        while q:
            lay,layer = list(),list()
            for node in q:
                layer.append(node.val)
                if node.left: lay.append(node.left)
                if node.right: lay.append(node.right)
            q = lay
            ans.append(layer.pop())
        return ans

    235. 二叉搜索树的最近公共祖先（model-V 祖先）

    题目链接：235. 二叉搜索树的最近公共祖先
    题目大意：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
    满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
    在这里插入图片描述

    例如：

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

    解题思路：配合 二叉搜索树的特点 即 左子树 < 根结点 < 右子树； 简化深度优先搜索。

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or p is None or q is None:
            return None
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left,p,q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right,p,q)
        return root
'
    运行

    236. 二叉树的最近公共祖先（model-V 祖先）

    题目链接：236. 二叉树的最近公共祖先
    题目大意：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
    最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

    例如：
    在这里插入图片描述

    输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

    解题思路： 这道题 只用文字描述 是非常乏力的，相对于 235. 二叉搜索树的最近公共祖先 难点主要体现在， 最近 这点上！ 可以看下一下 这篇题解 里面的图解非常不错。
    这道题 if 部分的思路主要是：（1）p=q=root 时 返回 root；（2）由于先返回的是 left 所以 left 存在 right 不存在 返回 left；（3）最后返回 right

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root == p or q == root:
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left:
            if right:
                return root
            return left
        return right
'
    运行

    1123. 最深叶节点的最近公共祖先（model-V 祖先）

    题目链接：1123. 最深叶节点的最近公共祖先
    题目大意：给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。
    回想一下：

    • 叶节点 是二叉树中没有子节点的节点
    • 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
    • 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，
    • 且 A 的深度达到此条件下可能的最大值。

    例如：
    在这里插入图片描述

    输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。

    解题思路： 看代码 吧！ DFS 万岁。

    # 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 lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:

        def dfs(root: Optional[TreeNode]) ->(TreeNode,int):
            if not root: return None,0
            leftT,leftD = dfs(root.left)
            rightT,rightD = dfs(root.right)
            if leftD == rightD:
                return root,leftD+1
            if leftD > rightD:
                return leftT,leftD+1
            else:
                return rightT,rightD+1
        
        return dfs(root)[0]

    110. 平衡二叉树（model-VI 平衡二叉树 model-II 的扩展 ）

    题目链接：110. 平衡二叉树
    题目大意：给定一个二叉树，判断它是否是高度平衡的二叉树。
    本题中，一棵高度平衡二叉树定义为：

    • 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

    例如：
    在这里插入图片描述

    输入：root = [3,9,20,null,null,15,7]
输出：true

    在这里插入图片描述

    输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

    解题思路： model-II 的扩展 需要左右子树的高度差 大于1 就返回 False。

    # 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root is None: return True
        L,R = self.maxDepth(root.left),self.maxDepth(root.right)
        return abs(L-R)<2 and self.isBalanced(root.left) and \
        self.isBalanced(root.right)

    def maxDepth(self,root:Optional[TreeNode]) -> int:
        if root is None: return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

    108. 将有序数组转换为二叉搜索树（model-VI 二叉搜索树）

    题目链接：104. 二叉树的最小深度
    题目大意：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
    高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

    例如：
    在这里插入图片描述
    在这里插入图片描述

    输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

    解题思路： 结合 二分法 的 深度优先搜索，进行建树。

    • 科普一下： 二叉查找树( Binary Search Tree,BST)是一种特殊的二叉树,又称为排序二叉树、二叉搜索树、二叉排序树。
    # 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:   

        def dfs(L: int,R: int) -> Optional[TreeNode]:
            if L>R: return None
            # For example, [-10,-3,0,5,9]
            # [0,-10,5,null,-3,null,9]
            mid = L+(R-L)//2
            # [0,-3,9,-10,null,5]
            # mid = L+(R-L+1)//2
            root = TreeNode(nums[mid])
            root.left = dfs(L,mid-1)
            root.right = dfs(mid+1,R)
            return root
        
        return dfs(0,len(nums)-1)

    总结

       今天有点累了，树 这部分的题目是真不不容易，还是 深度优先搜索算法 最好用，但理解起来真的吃力，后续会依次进行分析总结，努力，奋斗！

  • 相关阅读:
    基于单片机的车载酒精含量自检系统设计与实现
    Html 后端了解基础
    2023-10-11 LeetCode每日一题（）
    [springMVC学习]11、自定义拦截器
    stm32外部时钟为12MHZ，修改代码适配
    【verilog 设计】 reg有没有必要全部赋初值？
    （手工）【sqli-labs靶场1-4】GET请求、错误注入、单引号、双引号、括号闭合、字符型、整型
    Java BIO模型分析（提供单线程和多线程服务端代码示例）
    C++学习笔记——链表基础算法
    IDEA2020安装教程
  • 原文地址：https://blog.csdn.net/weixin_42269028/article/details/127079823