algorithm - 在二叉搜索树中找到第 k 个最小节点

Question

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int cnt = 0;
        int val = -1000;
        int res  = inorderTraversal(root,k,cnt,val);
        return res;
    }


    public int inorderTraversal(TreeNode root,int k,int cnt,int val){

         if (root == null) 
            return val; 

        inorderTraversal(root.left,k,cnt,val);
        cnt++;
        //System.out.println(root.val);
        if(cnt == k){
            //System.out.println(root.val);
            val = root.val;
            return val;
        }
        inorderTraversal(root.right,k,cnt,val);
        return val;
    }
}

所以我明白了，我可以使用中序遍历来找到第k小的节点。我无法理解，一旦找到它，我如何将它发送回递归的底部堆栈。我在这里没有得到答案。

注意:这不是家庭作业或任何作业。我对递归感到困惑并试图理解该方法

问题来自https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Answer 1

实际上，您可以使用调试器在执行递归时可视化堆栈帧。

让我们在一个简单的 BST 上分析它，例如:

      2

  1       3

从 root = 2 开始(TopStackFrame : { root = 2, k = 3, cnt = 0, val = -1000 })

|

root != null

|

所以转到 1(TopStackFrame: { root = 1, k = 3, cnt = 0, val = -1000 })

|

现在转到 1 的左侧(TopStackFrame: { root = null, k = 3, cnt = 0, val = -1000 })

|

root 为 null 它返回 val(移除堆栈顶部)

|

现在回到1

|

cnt++cnt 变为 1 (TopStackFrame: { root = 1, k = 3, cnt = 1, val = -1000 })

|

cnt != k转到 1 的右边(TopStackFrame: { root = null, k = 3 cnt = 1, val = -1000 })

|

1 的权利为空返回 val(移除栈顶)

|

然后再次返回 val (TopStackFrame: { root = 1, k = 3, cnt = 1, val = -1000 })

|

现在 1 完成了。

|

现在你来到 2 (TopStackFrame: { root = 2, k = 3, cnt = 0, val = -1000 })

现在你看到 cnt 的值不是 1 而是 0 了吗，因为每个堆栈框架都有自己的一组变量。

类似的事情发生在变量 val 上。

有几个选项可以解决这个问题:

a) 您可以在您的类中将这些声明为成员变量并在您的递归中更新它们，这样您就不需要通过递归返回任何内容，只需声明一个不返回任何内容但更新这些成员变量的方法。

b) 您可以使用像 int[] val、int[] cnt 这样的数组，每个数组包含一个元素，并在每次递归调用中更新它们的元素。

c) 您可以使用迭代中序遍历并在计数达到 k 时获取值。

我更喜欢“c”。它更简洁，不必声明成员变量或数组。它还可以防止高度不平衡树中的 stackoverflow 异常。