package
0.0.0-20240920062246-d0657495930a
Repository: https://github.com/yigmmk/leetcode.git
Documentation: pkg.go.dev
# Packages
* @lc app=leetcode.cn id=100 lang=golang
*
* [100] 相同的树
*
* https://leetcode.cn/problems/same-tree/description/
*
* algorithms
* Easy (59.89%)
* Likes: 1009
* Dislikes: 0
* Total Accepted: 449K
* Total Submissions: 749.6K
* Testcase Example: '[1,2,3]\n[1,2,3]'
*
* 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
*
* 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
*
*
*
* 示例 1：
*
*
* 输入：p = [1,2,3], q = [1,2,3]
* 输出：true
*
*
* 示例 2：
*
*
* 输入：p = [1,2], q = [1,null,2]
* 输出：false
*
*
* 示例 3：
*
*
* 输入：p = [1,2,1], q = [1,1,2]
* 输出：false
*
*
*
*
* 提示：
*
*
* 两棵树上的节点数目都在范围 [0, 100] 内
* -10^4
*
*
*/.
* @lc app=leetcode.cn id=104 lang=golang
*
* [104] 二叉树的最大深度
*
* https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
*
* algorithms
* Easy (77.19%)
* Likes: 1735
* Dislikes: 0
* Total Accepted: 1.1M
* Total Submissions: 1.5M
* Testcase Example: '[3,9,20,null,null,15,7]'
*
* 给定一个二叉树 root ，返回其最大深度。
*
* 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
*
*
*
* 示例 1：
*
*
*
*
*
*
* 输入：root = [3,9,20,null,null,15,7]
* 输出：3
*
*
* 示例 2：
*
*
* 输入：root = [1,null,2]
* 输出：2
*
*
*
*
* 提示：
*
*
* 树中节点的数量在 [0, 10^4] 区间内。
* -100 <= Node.val <= 100
*
*
*/.
* @lc app=leetcode.cn id=112 lang=golang
*
* [112] 路径总和
*
* https://leetcode.cn/problems/path-sum/description/
*
* algorithms
* Easy (53.71%)
* Likes: 1276
* Dislikes: 0
* Total Accepted: 602.6K
* Total Submissions: 1.1M
* Testcase Example: '[5,4,8,11,null,13,4,7,2,null,null,null,1]\n22'
*
* 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点
* 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
*
* 叶子节点 是指没有子节点的节点。
*
*
*
* 示例 1：
*
*
* 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
* 输出：true
* 解释：等于目标和的根节点到叶节点路径如上图所示。
*
*
* 示例 2：
*
*
* 输入：root = [1,2,3], targetSum = 5
* 输出：false
* 解释：树中存在两条根节点到叶子节点的路径：
* (1 --> 2): 和为 3
* (1 --> 3): 和为 4
* 不存在 sum = 5 的根节点到叶子节点的路径。
*
* 示例 3：
*
*
* 输入：root = [], targetSum = 0
* 输出：false
* 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
*
*
*
*
* 提示：
*
*
* 树中节点的数目在范围 [0, 5000] 内
* -1000 <= Node.val <= 1000
* -1000 <= targetSum <= 1000
*
*
*/.
* @lc app=leetcode.cn id=113 lang=golang
*
* [113] 路径总和 II
*
* https://leetcode.cn/problems/path-sum-ii/description/
*
* algorithms
* Medium (63.21%)
* Likes: 1055
* Dislikes: 0
* Total Accepted: 374.7K
* Total Submissions: 592.9K
* Testcase Example: '[5,4,8,11,null,13,4,7,2,null,null,5,1]\n22'
*
* 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
*
* 叶子节点 是指没有子节点的节点。
*
*
*
*
*
* 示例 1：
*
*
* 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
* 输出：[[5,4,11,2],[5,8,4,5]]
*
*
* 示例 2：
*
*
* 输入：root = [1,2,3], targetSum = 5
* 输出：[]
*
*
* 示例 3：
*
*
* 输入：root = [1,2], targetSum = 0
* 输出：[]
*
*
*
*
* 提示：
*
*
* 树中节点总数在范围 [0, 5000] 内
* -1000
* -1000
*
*
*
*
*/.
* @lc app=leetcode.cn id=1145 lang=golang
*
* [1145] 二叉树着色游戏
*
* https://leetcode.cn/problems/binary-tree-coloring-game/description/
*
* algorithms
* Medium (47.88%)
* Likes: 172
* Dislikes: 0
* Total Accepted: 19.3K
* Total Submissions: 36.1K
* Testcase Example: '[1,2,3,4,5,6,7,8,9,10,11]\n11\n3'
*
* 有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到
* n 各不相同。
*
* 最开始时：
*
*
* 「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；
* 「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。
*
*
* 「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。
*
* 之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，将所选节点一个 未着色
* 的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红色，「二号」玩家染蓝色）。
*
* 如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。
*
* 若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。
*
* 现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true ；若无法获胜，就请返回 false 。
*
*
* 示例 1 ：
*
*
* 输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
* 输出：true
* 解释：第二个玩家可以选择值为 2 的节点。
*
* 示例 2 ：
*
*
* 输入：root = [1,2,3], n = 3, x = 1
* 输出：false
*
*
*
*
* 提示：
*
*
* 树中节点数目为 n
* 1 <= x <= n <= 100
* n 是奇数
* 1 <= Node.val <= n
* 树中所有值 互不相同
*
*
*/.
* @lc app=leetcode.cn id=1161 lang=golang
*
* [1161] 最大层内元素和
*
* https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/description/
*
* algorithms
* Medium (65.62%)
* Likes: 125
* Dislikes: 0
* Total Accepted: 42.9K
* Total Submissions: 65.3K
* Testcase Example: '[1,7,0,7,-8,null,null]'
*
* 给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
*
* 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
*
*
*
* 示例 1：
*
*
*
*
* 输入：root = [1,7,0,7,-8,null,null]
* 输出：2
* 解释：
* 第 1 层各元素之和为 1，
* 第 2 层各元素之和为 7 + 0 = 7，
* 第 3 层各元素之和为 7 + -8 = -1，
* 所以我们返回第 2 层的层号，它的层内元素之和最大。
*
*
* 示例 2：
*
*
* 输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
* 输出：2
*
*
*
*
* 提示：
*
*
* 树中的节点数在 [1, 10^4]范围内
* -10^5 <= Node.val <= 10^5
*
*
*/.
* @lc app=leetcode.cn id=1372 lang=golang
*
* [1372] 二叉树中的最长交错路径
*
* https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/description/
*
* algorithms
* Medium (55.45%)
* Likes: 153
* Dislikes: 0
* Total Accepted: 22K
* Total Submissions: 39.6K
* Testcase Example: '[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]'
*
* 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
*
*
* 选择二叉树中 任意 节点和一个方向（左或者右）。
* 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
* 改变前进方向：左变右或者右变左。
* 重复第二步和第三步，直到你在树中无法继续移动。
*
*
* 交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
*
* 请你返回给定树中最长 交错路径 的长度。
*
*
*
* 示例 1：
*
*
*
* 输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
* 输出：3
* 解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
*
*
* 示例 2：
*
*
*
* 输入：root = [1,1,1,null,1,null,null,1,1,null,1]
* 输出：4
* 解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
*
*
* 示例 3：
*
* 输入：root = [1]
* 输出：0
*
*
*
*
* 提示：
*
*
* 每棵树最多有 50000 个节点。
* 每个节点的值在 [1, 100] 之间。
*
*
*/.
* @lc app=leetcode.cn id=199 lang=golang
*
* [199] 二叉树的右视图
*
* https://leetcode.cn/problems/binary-tree-right-side-view/description/
*
* algorithms
* Medium (66.21%)
* Likes: 987
* Dislikes: 0
* Total Accepted: 336.7K
* Total Submissions: 508.1K
* Testcase Example: '[1,2,3,null,5,null,4]'
*
* 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
*
*
*
* 示例 1:
*
*
*
*
* 输入: [1,2,3,null,5,null,4]
* 输出: [1,3,4]
*
*
* 示例 2:
*
*
* 输入: [1,null,3]
* 输出: [1,3]
*
*
* 示例 3:
*
*
* 输入: []
* 输出: []
*
*
*
*
* 提示:
*
*
* 二叉树的节点个数的范围是 [0,100]
* -100
*
*
*/.
* @lc app=leetcode.cn id=2331 lang=golang
*
* [2331] 计算布尔二叉树的值
*
* https://leetcode.cn/problems/evaluate-boolean-binary-tree/description/
*
* algorithms
* Easy (82.21%)
* Likes: 56
* Dislikes: 0
* Total Accepted: 22.9K
* Total Submissions: 27.1K
* Testcase Example: '[2,1,3,null,null,0,1]'
*
* 给你一棵 完整二叉树 的根，这棵树有以下特征：
*
*
* 叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
* 非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。
*
*
* 计算 一个节点的值方式如下：
*
*
* 如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
* 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。
*
*
* 返回根节点 root 的布尔运算值。
*
* 完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
*
* 叶子节点 是没有孩子的节点。
*
*
*
* 示例 1：
*
*
*
* 输入：root = [2,1,3,null,null,0,1]
* 输出：true
* 解释：上图展示了计算过程。
* AND 与运算节点的值为 False AND True = False 。
* OR 运算节点的值为 True OR False = True 。
* 根节点的值为 True ，所以我们返回 true 。
*
* 示例 2：
*
* 输入：root = [0]
* 输出：false
* 解释：根节点是叶子节点，且值为 false，所以我们返回 false 。
*
*
*
*
* 提示：
*
*
* 树中节点数目在 [1, 1000] 之间。
* 0 <= Node.val <= 3
* 每个节点的孩子数为 0 或 2 。
* 叶子节点的值为 0 或 1 。
* 非叶子节点的值为 2 或 3 。
*
*
*/.
* @lc app=leetcode.cn id=236 lang=golang
*
* [236] 二叉树的最近公共祖先
*
* https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
*
* algorithms
* Medium (70.14%)
* Likes: 2508
* Dislikes: 0
* Total Accepted: 609.5K
* Total Submissions: 868K
* Testcase Example: '[3,5,1,6,2,0,8,null,null,7,4]\n5\n1'
*
* 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
*
* 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x
* 的深度尽可能大（一个节点也可以是它自己的祖先）。”
*
*
*
* 示例 1：
*
*
* 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
* 输出：3
* 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
*
*
* 示例 2：
*
*
* 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
* 输出：5
* 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
*
*
* 示例 3：
*
*
* 输入：root = [1,2], p = 1, q = 2
* 输出：1
*
*
*
*
* 提示：
*
*
* 树中节点数目在范围 [2, 10^5] 内。
* -10^9
* 所有 Node.val 互不相同 。
* p != q
* p 和 q 均存在于给定的二叉树中。
*
*
*/.
* @lc app=leetcode.cn id=437 lang=golang
*
* [437] 路径总和 III
*
* https://leetcode.cn/problems/path-sum-iii/description/
*
* algorithms
* Medium (49.24%)
* Likes: 1747
* Dislikes: 0
* Total Accepted: 255.9K
* Total Submissions: 521.2K
* Testcase Example: '[10,5,-3,3,2,null,11,3,-2,null,1]\n8'
*
* 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
*
* 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
*
*
*
* 示例 1：
*
*
*
*
* 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
* 输出：3
* 解释：和等于 8 的路径有 3 条，如图所示。
*
*
* 示例 2：
*
*
* 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
* 输出：3
*
*
*
*
* 提示:
*
*
* 二叉树的节点个数的范围是 [0,1000]
* -10^9
* -1000
*
*
*/.
* @lc app=leetcode.cn id=450 lang=golang
*
* [450] 删除二叉搜索树中的节点
*
* https://leetcode.cn/problems/delete-node-in-a-bst/description/
*
* algorithms
* Medium (52.33%)
* Likes: 1265
* Dislikes: 0
* Total Accepted: 233.4K
* Total Submissions: 446K
* Testcase Example: '[5,3,6,2,4,null,7]\n3'
*
* 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key
* 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
*
* 一般来说，删除节点可分为两个步骤：
*
*
* 首先找到需要删除的节点；
* 如果找到了，删除它。
*
*
*
*
* 示例 1:
*
*
*
*
* 输入：root = [5,3,6,2,4,null,7], key = 3
* 输出：[5,4,6,2,null,null,7]
* 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
* 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
* 另一个正确答案是 [5,2,6,null,4,null,7]。
*
*
*
*
* 示例 2:
*
*
* 输入: root = [5,3,6,2,4,null,7], key = 0
* 输出: [5,3,6,2,4,null,7]
* 解释: 二叉树不包含值为 0 的节点
*
*
* 示例 3:
*
*
* 输入: root = [], key = 0
* 输出: []
*
*
*
* 提示:
*
*
* 节点数的范围 [0, 10^4].
* @lc app=leetcode.cn id=687 lang=golang
*
* [687] 最长同值路径
*
* https://leetcode.cn/problems/longest-univalue-path/description/
*
* algorithms
* Medium (47.77%)
* Likes: 782
* Dislikes: 0
* Total Accepted: 84.8K
* Total Submissions: 177.3K
* Testcase Example: '[5,4,5,1,1,null,5]'
*
* 给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
*
* 两个节点之间的路径长度 由它们之间的边数表示。
*
*
*
* 示例 1:
*
*
*
*
* 输入：root = [5,4,5,1,1,5]
* 输出：2
*
*
* 示例 2:
*
*
*
*
* 输入：root = [1,4,5,4,4,5]
* 输出：2
*
*
*
*
* 提示:
*
*
* 树的节点数的范围是 [0, 10^4]
* -1000 <= Node.val <= 1000
* 树的深度将不超过 1000
*
*
*/.
* @lc app=leetcode.cn id=700 lang=golang
*
* [700] 二叉搜索树中的搜索
*
* https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
*
* algorithms
* Easy (77.74%)
* Likes: 448
* Dislikes: 0
* Total Accepted: 288.6K
* Total Submissions: 371K
* Testcase Example: '[4,2,7,1,3]\n2'
*
* 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
*
* 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
*
*
*
* 示例 1:
*
*
*
*
* 输入：root = [4,2,7,1,3], val = 2
* 输出：[2,1,3]
*
*
* 示例 2:
*
*
* 输入：root = [4,2,7,1,3], val = 5
* 输出：[]
*
*
*
*
* 提示：
*
*
* 数中节点数在 [1, 5000] 范围内
* 1 <= Node.val <= 10^7
* root 是二叉搜索树
* 1 <= val <= 10^7
*
*
*/.
* @lc app=leetcode.cn id=95 lang=golang
*
* [95] 不同的二叉搜索树 II
*
* https://leetcode.cn/problems/unique-binary-search-trees-ii/description/
*
* algorithms
* Medium (73.23%)
* Likes: 1416
* Dislikes: 0
* Total Accepted: 165.1K
* Total Submissions: 225.4K
* Testcase Example: '3'
*
* 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
*
*
*
*
*
* 示例 1：
*
*
* 输入：n = 3
* 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
*
*
* 示例 2：
*
*
* 输入：n = 1
* 输出：[[1]]
*
*
*
*
* 提示：
*
*
* 1
*
*
*
*
*/.
No description provided by the author
* @lc app=leetcode.cn id=99 lang=golang
*
* [99] 恢复二叉搜索树
*
* https://leetcode.cn/problems/recover-binary-search-tree/description/
*
* algorithms
* Medium (60.27%)
* Likes: 855
* Dislikes: 0
* Total Accepted: 133.1K
* Total Submissions: 220.8K
* Testcase Example: '[1,3,null,null,2]'
*
* 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
*
*
*
* 示例 1：
*
*
* 输入：root = [1,3,null,null,2]
* 输出：[3,1,null,null,2]
* 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
*
*
* 示例 2：
*
*
* 输入：root = [3,1,4,null,null,2]
* 输出：[2,1,4,null,null,3]
* 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
*
*
*
* 提示：
*
*
* 树上节点的数目在范围 [2, 1000] 内
* -2^31 <= Node.val <= 2^31 - 1
*
*
*
*
* 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
*
*/.