相同的树-LeetCode
100. 相同的树 - Same Tree 🎯 问题描述（来源于LeetCode） 描述： 给定两个二叉树的根节点 p 和 q，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 说明： 两棵树均由 TreeNode 节点组成，每个节点包含整数值 val 以及指向左子节点 left 和右子节点 right 的指针。 空树用 None 表示。 示例： 示例 1： 12输入: p = [1,2,3], q = [1,2,3]输出: true 示例 2： 12输入: p = [1,2], q = [1,null,2]输出: false 💻 解题思路 思路1：递归深度优先比较（DFS） 算法步骤 处理空节点情况： 如果 p 或 q 有一个是 None（空节点），则只有当两者同时为 None 时才算相同，否则不同。 等价于：若其中一个为 None，则返回 p == q（即 p is None and q is None）。 比较当前节点值： 如果当前两个节点都不为空，则先比较它们的 val 是否相...
翻转等价二叉树-LeetCode
951. 翻转等价二叉树 - Flip Equivalent Binary Trees 🎯 问题描述（来源于LeetCode） 描述： 给定两棵二叉树的根节点 root1 和 root2，判断它们是否翻转等价。 定义：如果可以通过执行若干次“翻转”操作（交换任意节点的左右子节点）使一棵树变成另一棵树，则两棵树翻转等价。 说明： “翻转”操作可以应用在任意节点上，次数不限。 空树与自身翻转等价。 示例： 示例 1： 12输入: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]输出: true 示例 2： 12输入: root1 = [], root2 = []输出: true 示例 3： 12输入: root1 = [], root2 = [1]输出: false 💻 解题思路 思路1：递归 + 分情况讨论（翻转 / 不翻转） 算法步骤 处理空节点： 如果 root1 或 root2 有一个为 None，则只有两...
计算布尔二叉树的值-LeetCode
2331. 计算布尔二叉树的值 - Evaluate Boolean Binary Tree 🎯 问题描述（来源于LeetCode） 描述： 给你一棵完整二叉树的根节点 root，这棵树有以下性质： 叶子节点的值为 0 或 1，其中 0 表示 False，1 表示 True。 非叶子节点的值为 2 或 3，其中 2 表示逻辑或（OR），3 表示逻辑与（AND）。 计算该布尔二叉树的值，返回 True 或 False。 说明： 完整二叉树指每个非叶子节点都有两个子节点。 计算规则：对于非叶子节点，先递归计算左右子树的值，然后根据节点值应用对应的逻辑运算。 示例： 示例 1： 123输入: root = [2,1,3,null,null,0,1]输出: true解释: 根节点值为2（OR），左叶子值为1 → true，右子树根值为3（AND），其左叶子0 → false，右叶子1 → true，AND结果 false，整体 OR(true, false) = true 示例 2： 12输入: root = [0]输出: false 💻 解题思路 思路1：递...
分裂二叉树的最大乘积-LeetCode
分裂二叉树的最大乘积 🎯 问题描述 给你一棵二叉树，它的根为 root。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。 由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。 （注意：需要在取模之前最大化乘积，而不是取模之后） 💻 解题思路 思路一：一次 DFS + 数组收集 核心思想： 通过一次 DFS 后序遍历，计算出每个节点为根的子树和，并全部存入数组 co_sum 中。 遍历结束后，数组中包含了所有可能切分出来的子树和。 遍历数组，利用公式 子树和 * (总和 - 子树和) 找出最大乘积。 代码实现 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263from typing import Optional# Definition for a binary tree node.# class TreeNode:# def __ini...
单值二叉树-LeetCode
单值二叉树 🎯 问题描述 如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时，才返回 true；否则返回 false。 💻 解题思路 思路一：基准值对比法 核心思想：整棵树的所有节点都必须等于根节点的值。我们在外部提取根节点的值作为基准，递归检查每一个节点是否等于该基准值。 代码实现 123456789101112131415161718192021222324252627282930313233343536373839from typing import Optional# 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 = rightclass Solution: def isUnivalTree(self, roo...
从叶结点开始的最小字符串-LeetCode
从叶结点开始的最小字符串 🎯 问题描述（来源于LeetCode） 描述： 给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。 返回按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。 说明： 字符串中任何较短的前缀在字典序上都是较小的（例如 "ab" 比 "aba" 小）。 叶结点是指没有子结点的结点。 示例： 示例 1：12输入：root = [0,1,2,3,4,3,4]输出："dba" 示例 2：12输入：root = [25,1,3,1,3,0,2]输出："adz" 💻 解题思路 思路：DFS 深度优先搜索（路径拼接与反转） 代码实现 from typing import Optional class Solution: def smallestFromLeaf(self, root: Optional[TreeNode]) -> str: ...
从根到叶的二进制数之和-LeetCode
从根到叶的二进制数之和 🎯 问题描述 给出一棵二叉树，其上每个结点的值都是 0 或 1。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。返回所有叶子节点对应的二进制数之和。 💻 解题思路 思路一：字符串拼接法（直观易懂） 在 DFS 过程中将节点值拼接成二进制字符串，到达叶子节点时使用 int(string, 2) 转换为十进制。 优点：代码极其直观，符合人类阅读二进制数的习惯。 缺点：字符串拼接会产生大量临时对象，且每次转换都需要重新计算，效率较低。 思路二：位运算动态维护（最优解） 在 DFS 过程中，每向下走一层，就将当前的十进制数值左移一位（乘以 2），再加上当前节点的值。 公式：cur_val = (cur_val << 1) | node.val 或 cur_val = cur_val * 2 + node.val。 优点：直接在数字层面进行运算，时间复杂度和空间复杂度都达到最优。 代码实现 from typing import Optional class Solution: def sumRootToLeaf...
在二叉树中增加一行-LeetCode
在二叉树中增加一行 🎯 问题描述 给定一个二叉树的根 root 和两个整数 val 和 depth，在给定的深度 depth 处添加一行值为 val 的节点。 根节点 root 的深度为 1。 添加规则：对于深度为 depth - 1 的每一非空节点 N，创建两个值为 val 的节点作为 N 的左右子树。N 原先的左子树作为新左节点的左子树，N 原先的右子树作为新右节点的右子树。 特殊情况：如果 depth == 1，则创建一个新的根节点，原整棵树作为新根的左子树。 💻 解题思路 思路一：DFS 深度优先搜索（你的解法） 核心思想：利用递归向下遍历，当到达目标深度的上一层（即 depth - 1 层）时，进行节点的插入和指针的重新指向。 代码实现 from typing import Optional # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val =...
祖父节点值为偶数的节点和-LeetCode
祖父节点值为偶数的节点和 🎯 问题描述（来源于LeetCode） 描述： 给你一棵二叉树，请你返回满足以下条件的所有节点的值之和： 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。） 如果不存在祖父节点值为偶数的节点，那么返回 0。 示例： 示例 1：123输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]输出：18解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。 💻 解题思路 思路1：DFS 深度优先搜索（状态传递） 代码实现 from typing import Optional class Solution: def sumEvenGrandparent(self, root: Optional[TreeNode]) -> int: ans = 0 def dfs(node, f=None, g=None): if node is None: ...
节点与其祖先之间的最大差值-LeetCode
节点与其祖先之间的最大差值 🎯 问题描述（来源于LeetCode） 描述： 给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。 （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先） 说明： 节点 A 是 B 的祖先，意味着 A 在从根节点到 B 的路径上。 题目本质是求：在任意一条从根到叶子的路径上，最大值与最小值的差的最大值。 示例： 示例 1：123456789输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]输出：7解释：我们有大量的节点与其祖先的差值，其中一些如下：|8 - 3| = 5|3 - 7| = 4|8 - 1| = 7|10 - 13| = 3在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。 💻 解题思路 思路：DFS 深度优先搜索（状态传递） 代码实现 from typing import Optional ...
