230.二叉搜索树中第k小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

思路

  • k--应该在访问该节点之前，否则，在递归结束之后可能k==1的情况可能再次出现
  • java对于普通变量是传递形参
  • 解决变量值传递的问题，可以用全局变量或者数组

方法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int ans=0;
    int count=0;
    public int kthSmallest(TreeNode root, int k) {
        count=k;
        midSearch(root);
        return ans;
    }
    private void midSearch(TreeNode root){
        if(root==null) return;
        midSearch(root.left);
        count--;
        if(count==0) {
            ans=root.val;
            return;
        }
        midSearch(root.right);
    }
}

方法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int[] nums=new int[2];
        nums[0]=k;
        midSearch(root,nums);
        return nums[1];
    }
    private void midSearch(TreeNode root,int[] nums){
        if(root==null) return;
        midSearch(root.left,nums);
        nums[0]--;
        if(nums[0]==0) {
            nums[1]=root.val;
            return;
        }
        midSearch(root.right,nums);
        return;
    }
}