在二叉搜索树中找到第 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;
    }
}

所以我明白了，我可以用inorder traversal找到第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 它 returns 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的权利为空 returns val（移除堆栈顶部）

|

然后再次 return 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) 您可以在 class 中将这些声明为成员变量并在递归中更新它们，这样您就不需要 return 任何递归，只需声明一个不需要的方法return除了更新这些成员变量之外的任何内容。

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

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

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

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

Find the kth smallest node in binary search tree

algorithm

tree-traversal

binary-search-tree

data-structures