第 K 个最小的元素

Question

我想找到第k小的元素。而且，不寻找额外的 space。

我写了这个但没有得到实际输出

/**
 * 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);

第 K 个最小的元素

Kth smallest element

tree

binary-tree