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 是树的高度。

解题思路

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

代码思路

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

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

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

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

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

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

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

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; // 返回弹出节点的值
    }

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

解题思路

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

代码思路

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

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

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

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

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

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

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

接着，它将新路径的价格与当前的最大路径和进行比较，更新maxSum变量的值。最后，它返回当前节点的值加上左右子树中增益较大的那个值，作为以当前节点为起点的最大路径和。
```
   // 更新最大路径和
        maxSum = Math.max(maxSum, priceNewpath);
```
通过递归地遍历整个二叉树，该方法可以找到从根节点到任意叶子节点的最大路径和，并将其存储在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

解题思路

初始化 patches 为 0，表示需要补充的数字个数；i 为 0，表示当前处理的 nums 数组中的索引；miss 为 1，表示当前未覆盖的数字范围的最小值。
当 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。
返回 patches。

代码思路

初始化变量patches为0，表示已经使用的补丁数量；变量i为0，表示当前处理的nums数组中的索引；变量miss为1，表示当前未覆盖的数字范围的最小值。
```
   // 初始化变量patches为0，i为0，miss为1
        int patches = 0, i = 0;
        long miss = 1;
```
当miss小于等于n时，执行循环。这是因为我们需要确保覆盖从1到n的所有数字。

在循环中，首先检查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加1
            if (i < nums.length && nums[i] <= miss)
                miss += nums[i++];

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

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

循环结束后，返回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;
    }
}