230。BST中的第k个最小元素
230。BST中的第k个最小元素
提问于 2021-10-14 05:02:37
在c++中，我们可以通过另一个函数中的指针和引用来更改变量的值，但在java中不能这样做。让我们回到查询上
这是问题描述，给定二进制搜索树的根，以及一个整数k，返回树中所有节点的值的第k个最小值(1-索引)。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
Integer cnt = 1, ans = 0;
traverse(root, k , cnt, ans);
return ans;
}
void traverse(TreeNode root, int k, Integer cnt, Integer ans){
if(root == null) return;
traverse(root.left, k, cnt, ans);
if(cnt++ == k){
ans = new Integer(root.val);
return;
}
traverse(root.right, k, cnt, ans);
}
}假设我想通过遍历函数改变ans的值，这个函数是空的，没有返回任何东西，但是我想改变ans的值，我该怎么做呢？因为程序的逻辑不依赖于语言，所以应该有一种方法来解决这个问题，ans的值最初是零，对于任何输入，ans的值都是零
Stack Overflow用户
回答已采纳
发布于 2021-10-14 07:47:13
逻辑不依赖于语言并不意味着实现也不依赖于语言。想象一下，在一种没有可变状态的纯函数式语言中实现逻辑-逻辑仍然是相同的，但实现需要非常不同。
要解决这个问题，您的递归函数需要更新两个值(cnt和ans)，这使得这个问题对于通常的风格(直接返回结果)来说有点笨拙。
相反，我会用一个helper对象来实现：
class Solution {
public int kthSmallest(TreeNode root, int k) {
Traverser t = new Traverser();
t.traverse(root, k);
return t.ans;
}
static class Traverser {
int cnt = 1;
int ans = 0;
void traverse(TreeNode root, int k) {
if (root == null) return;
traverse(root.left, k);
if (cnt++ == k) {
ans = root.val;
return;
}
traverse(root.right, k);
}
}
}请注意，Traverser.traverse()方法与您的traverse实现非常一致--只有两个参数ans和cnt被迁移到了Traverser类的字段中。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69565317
复制相关文章
相似问题
腾讯云开发者
