当前版本号[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 是树的高度。
这段代码实现了一个二叉搜索树的迭代器。
首先定义了一个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
首先定义了一个名为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,表示当前未覆盖的数字范围的最小值。
// 初始化变量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;
}
}