在 BST 中找到第 K 个最小值 -- K 不变

Question

我考虑了很久这个问题，我的脑子都快炸了。可能我还没有完全理解递归。

我不明白为什么k的值在等于0之后不进入负数。相反，它保持为 0，直到辅助函数存在。我尝试传入一个初始值为零的整数并添加直到它的值等于 k。然而，这导致了同样的问题，一旦它等于 k，它就保持不变。

有人可以解释为什么值保持不变吗？

class Solution {
        public int kthSmallest(TreeNode t, int k) {
          TreeNode tempNode = new TreeNode();
          int iter = 0;
          getKValue(t, k, tempNode); 
          return tempNode.val;
        }
        
        private static void getKValue(TreeNode t, int k, TreeNode temp) {
            if(t == null) {
                return;
            }
        
    
            getKValue(t.left, k, temp);
            
            
            k = k - 1;
            System.out.println(k);
            if(k == 0) {
                temp.val = t.val;
                return;
            }
            getKValue(t.right, k, temp);
        
        }
    }

例如，对于下面的树，预期输出是 1。但我得到 3，控制台打印两次 0。

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Answer 1

我认为问题是因为您在每个递归调用中都传递了 k。您不应该这样做，因为这会导致每个递归调用都获得自己的 k 的 copy。这意味着当你修改 k:

k = k - 1;

堆栈中的其他调用不知道 k 变化。至于其他调用，k仍然是1，因为它们各自有自己的副本。

要解决此问题，您应该有一个 shared k，所有递归调用都可以访问：

    static int sharedK; // shared!
    public int kthSmallest(TreeNode t, int k) {
      TreeNode tempNode = new TreeNode();
      sharedK = k; // setting the sharedK
      getKValue(t, tempNode); 
      return tempNode.val;
    }
    
    private static void getKValue(TreeNode t, TreeNode temp) {
        if(t == null) {
            return;
        }

        getKValue(t.left, temp);
        
        sharedK--; // note the change here
        System.out.println(sharedK);
        if(sharedK == 0) {
            temp.val = t.val;
            return;
        }
        getKValue(t.right, temp);
    }

如果 k 通过引用传递也可以实现同样的效果，但不幸的是你不能在 Java 中通过引用传递。

Answer 2

我认为这个问题需要你输出 BST 的第 K 个最小元素，这是使用 O(N) 内存的代码 space，其中 N 是 BST 中的节点数。首先，我们将使用 in-order 遍历（递归）遍历 BST，并将节点保存在数组或向量中。 In-order BST 遍历按排序顺序给出节点。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

vector<int> nodes;

void inorder(TreeNode *root) {
    if(root!=NULL)
    {
        inorder(root->left);
        nodes.push_back(root->val);
        inorder(root->right);
    }
}
class Solution {
public:
    int getValue(TreeNode* root,int K)
    {
        nodes.clear();
        if(root!=NULL)
        {
            inorder(root);
            return nodes[K-1];
        }
        return -1;
    }
};

在 BST 中找到第 K 个最小值 -- K 不变

Find Kth Smallest Value in BST -- K not changing

java

algorithm

recursion

binary-tree

depth-first-search