第k个最小元素

Question

我想找出第k个最小的元素。而且，不需要额外的空间。

我写了这篇文章，但没有得到实际的输出。

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */
public class Solution {

    public int kthsmallest(TreeNode A, int B) {
        int find=kth(A,B,-1);
        System.out.println(find);
        return find;
    }
    public static int kth(TreeNode A,int B,int val)
    {
       // System.out.print("k  "+k);

        if(val!=-1)
        return val;
        if(A==null)
        {

            return -1;
        }

        kth(A.left,B,val);
        B--;
        if(0==B)
        {
            val=A.val;
            //System.out.print("bbbb"+val);
            return A.val;
        }
        //System.out.print(" :k lv: "+k);
        kth(A.right,B,val);
        if(0==B)
        {
            val=A.val;
            //System.out.print("xdf"+val);
            return A.val;
        }



        return val;


    }
}

Answer 1

问题是，在找到元素后，您不会传播它。替换该行：

kth(A.left,B,val);

通过以下方式：

int v=kth(A.left,B,val);
if (v != -1) {return v;}

同样适用于：

kth(A.right,B,val);