CSDN每日一题学习训练——Java版（二叉搜索树迭代器、二叉树中的最大路径和、按要求补齐数组）

版本说明

当前版本号[20231115]。

版本	修改说明
20231115	初版

目录

二叉搜索树迭代器

题目

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 105] 内
0 <= Node.val <= 106
最多调用 105 次 hasNext 和 next 操作

进阶：

你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

解题思路

1. 初始化一个空栈，用于存储中序遍历过程中的节点。
2. 从根节点开始，将所有左子节点依次入栈，直到遇到没有左子节点的节点。
3. 当栈不为空时，弹出栈顶元素，将其值返回，并将其右子节点依次入栈，直到遇到没有右子节点的节点。
4. 重复步骤2和3，直到栈为空。

代码思路

1. 这段代码实现了一个二叉搜索树的迭代器。

2. 首先定义了一个TreeNode类，表示二叉树的节点，包含一个整数值val和左右子节点left、right。

   // 定义一个二叉树节点类
   public class TreeNode {int val; // 节点值TreeNode left; // 左子节点TreeNode right; // 右子节点// 构造函数，初始化节点值TreeNode(int x) {val = x;}
   }
   

3. 然后定义了一个BSTIterator类，用于实现二叉搜索树的迭代器。这个迭代器使用了一个LinkedList来存储遍历过程中的节点。

   // 定义一个二叉搜索树迭代器类
   class BSTIterator {LinkedList<TreeNode> stack = new LinkedList<>(); // 使用链表存储遍历过程中的节点
   

4. 在构造函数中，将根节点root及其左子树的所有节点依次入栈。这样，栈顶元素就是当前最小的节点。

     // 构造函数，接收根节点作为参数，将根节点及其左子树的所有节点依次入栈public BSTIterator(TreeNode root) {TreeNode cur = root;while (cur != null) {stack.push(cur);cur = cur.left;}}
   

5. next()方法用于获取下一个节点的值。首先弹出栈顶元素，然后将该节点的右子树及其左子树的所有节点依次入栈。这样，下一次调用next()方法时，栈顶元素就是当前最小的节点。

    // next() 方法，返回下一个节点的值public int next() {TreeNode n = stack.pop(); // 弹出栈顶元素TreeNode cur = n.right; // 获取弹出节点的右子节点while (cur != null) {stack.push(cur); // 将右子节点及其左子树的所有节点依次入栈cur = cur.left;}return n.val; // 返回弹出节点的值}
   

6. hasNext()方法用于判断是否还有下一个节点。只要栈不为空，就说明还有下一个节点。

    // hasNext() 方法，判断是否还有下一个节点public boolean hasNext() {return !stack.isEmpty(); // 如果栈不为空，则说明还有下一个节点}
   

参考代码

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}
class BSTIterator {LinkedList<TreeNode> stack = new LinkedList<>();public BSTIterator(TreeNode root) {TreeNode cur = root;while (cur != null) {stack.push(cur);cur = cur.left;}}public int next() {TreeNode n = stack.pop();TreeNode cur = n.right;while (cur != null) {stack.push(cur);cur = cur.left;}return n.val;}public boolean hasNext() {return !stack.isEmpty();}
}
/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj = new BSTIterator(root);* int param_1 = obj.next();* boolean param_2 = obj.hasNext();*/

二叉树中的最大路径和

题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

解题思路

1. 初始化一个全局变量 maxSum，用于存储最大路径和，初始值为 Integer.MIN_VALUE。
2. 定义一个递归函数 maxGain，输入参数为 TreeNode 类型的节点 node。
3. 如果节点为空，返回 0。
4. 计算左子树的最大增益 leftGain，如果小于等于 0，则取 0。
5. 计算右子树的最大增益 rightGain，如果小于等于 0，则取 0。
6. 计算新路径的价格 priceNewpath，即当前节点的值加上左右子树的最大增益。
7. 更新 maxSum，将其设置为 maxSum 和 priceNewpath 中的较大值。
8. 返回当前节点的值加上左右子树中增益较大的那个值。
9. 在 maxPathSum 函数中调用 maxGain 函数，并返回 maxSum。

代码思路

1. 首先定义了一个名为Solution的类，其中包含一个名为maxSum的整数变量，用于存储最大路径和。

   // 定义一个名为Solution的类
   class Solution {// 初始化最大路径和为整数最小值int maxSum = Integer.MIN_VALUE;// 定义一个名为maxPathSum的方法，接收一个TreeNode类型的参数root，返回一个整数值
   

2. maxPathSum(TreeNode root)：这是主方法，它接受一个二叉树的根节点作为参数，并返回最大路径和。在这个方法中，首先调用maxGain方法来计算最大路径和，然后返回maxSum变量的值。

    public int maxPathSum(TreeNode root) {// 调用maxGain方法计算最大路径和maxGain(root);// 返回最大路径和return maxSum;}
   

3. maxGain(TreeNode node)：这是一个辅助方法，用于递归地计算以给定节点为起点的最大路径和。它首先检查节点是否为空，如果为空则返回0。

       // 定义一个名为maxGain的方法，接收一个TreeNode类型的参数node，返回一个整数值public int maxGain(TreeNode node) {// 如果节点为空，返回0if (node == null) {return 0;}
   

4. 然后，它分别计算左子树和右子树的最大增益（即不选择该子树的情况下的最大路径和），并将它们与当前节点的值相加得到新路径的价格。

      // 计算左子树的最大增益，如果小于0则取0int leftGain = Math.max(maxGain(node.left), 0);// 计算右子树的最大增益，如果小于0则取0int rightGain = Math.max(maxGain(node.right), 0);// 计算新路径的价格int priceNewpath = node.val + leftGain + rightGain;
   

5. 接着，它将新路径的价格与当前的最大路径和进行比较，更新maxSum变量的值。最后，它返回当前节点的值加上左右子树中增益较大的那个值，作为以当前节点为起点的最大路径和。

      // 更新最大路径和maxSum = Math.max(maxSum, priceNewpath);
   

6. 通过递归地遍历整个二叉树，该方法可以找到从根节点到任意叶子节点的最大路径和，并将其存储在maxSum变量中。最终，maxPathSum方法将返回这个最大路径和。

    // 返回当前节点的值加上左右子树中增益较大的那个值return node.val + Math.max(leftGain, rightGain);
   

参考代码

这段代码是二叉树路径和的最大值问题。

class Solution {int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}public int maxGain(TreeNode node) {if (node == null) {return 0;}int leftGain = Math.max(maxGain(node.left), 0);int rightGain = Math.max(maxGain(node.right), 0);int priceNewpath = node.val + leftGain + rightGain;maxSum = Math.max(maxSum, priceNewpath);return node.val + Math.max(leftGain, rightGain);}
}

按要求补齐数组

题目

给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

示例 1:

输入: nums =
[1,3]
, n =
6

输出: 1
解释:
根据 nums 里现有的组合
[1], [3], [1,3]
，可以得出
1, 3, 4
。
现在如果我们将
2
添加到 nums 中， 组合变为:
[1], [2], [3], [1,3], [2,3], [1,2,3]
。
其和可以表示数字
1, 2, 3, 4, 5, 6
，能够覆盖
[1, 6]
区间里所有的数。
所以我们最少需要添加一个数字。

示例 2:

输入: nums =
[1,5,10]
, n =
20

输出: 2
解释: 我们需要添加
[2, 4]
。

示例 3:

输入: nums =
[1,2,2]
, n =
5

输出: 0

解题思路

1. 初始化 patches 为 0，表示需要补充的数字个数；i 为 0，表示当前处理的 nums 数组中的索引；miss 为 1，表示当前未覆盖的数字范围的最小值。
2. 当 miss <= n 时，执行循环： a. 如果 i < nums.length 且 nums[i] <= miss，说明可以用 nums[i] 来表示 miss，将 miss 加上 nums[i]，并将 i 向右移动一位。 b. 否则，说明需要补充一个数字，使得 miss 可以表示为两个数的和，即 miss = miss + miss。将 miss 加上 miss，并将 patches 加 1。
3. 返回 patches。

代码思路

1. 初始化变量patches为0，表示已经使用的补丁数量；变量i为0，表示当前处理的nums数组中的索引；变量miss为1，表示当前未覆盖的数字范围的最小值。

      // 初始化变量patches为0，i为0，miss为1int patches = 0, i = 0;long miss = 1;
   

2. 当miss小于等于n时，执行循环。这是因为我们需要确保覆盖从1到n的所有数字。

3. 在循环中，首先检查i是否小于nums的长度且nums[i]小于等于miss。如果是，则说明我们可以使用nums[i]来扩展当前的覆盖范围，因此将miss加上nums[i]并将i加1。

    // 当miss小于等于n时，执行循环while (miss <= n) {// 如果i小于nums的长度且nums[i]小于等于miss，则将miss加上nums[i]并将i加1if (i < nums.length && nums[i] <= miss)miss += nums[i++];
   

4. 如果上述条件不满足，说明我们需要增加一个新的补丁来扩展当前的覆盖范围。此时，将miss加上miss（即当前未覆盖的数字范围的最小值），并将patches加1。

    // 否则，将miss加上miss，并将patches加1else {miss += miss;patches++;}
   

5. 循环结束后，返回patches的值，即所需的最少补丁数量。

        // 返回patches的值return patches;

参考代码

这段代码是计算将1到n之间的所有数字都覆盖所需要的最少的补丁数量。

class Solution {public int minPatches(int[] nums, int n) {int patches = 0, i = 0;long miss = 1;while (miss <= n) {if (i < nums.length && nums[i] <= miss)miss += nums[i++];else {miss += miss;patches++;}}return patches;}
}