当前位置：首页 > news >正文

微网站页面厚街做网站公司

news 2025/9/17 21:56:55

微网站页面,厚街做网站公司,做一个公司官网需要多少钱,合肥企业网站版本说明当前版本号[20231115]。版本修改说明20231115初版目录文章目录版本说明目录二叉搜索树迭代器题目解题思路代码思路参考代码二叉树中的最大路径和题目解题思路代码思路参考代码按要求补齐数组题目解题思路代码思路参考代码二叉搜索树迭代器题目实现一个二…

版本说明

当前版本号[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) {// 如果节点为空，返回0if (node == null) {return 0;}

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

   // 计算左子树的最大增益，如果小于0则取0int leftGain = Math.max(maxGain(node.left), 0);// 计算右子树的最大增益，如果小于0则取0int 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为1int 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加1if (i < nums.length && nums[i] <= miss)miss += nums[i++];

如果上述条件不满足，说明我们需要增加一个新的补丁来扩展当前的覆盖范围。此时，将miss加上miss（即当前未覆盖的数字范围的最小值），并将patches加1。
```
 // 否则，将miss加上miss，并将patches加1else {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;}
}