二叉搜索树的第k个节点

int cnt;
public int KthNode (TreeNode proot, int k) {
    // write code here
    cnt=k;
    return dfs(proot);

}

public int dfs(TreeNode root){
    if(root==null){
        return -1;
    }
    int left = dfs(root.left);
    if(--cnt==0){
        return root.val;
    }
    int right=dfs(root.right);
    return Math.max(left ,right);
}

public int KthNode (TreeNode proot, int k) {

    // write code here

    if (proot == null) return -1;

    //int n = GetNodeNum(proot);

    ArrayListInteger> tree = new ArrayList();

    tree = inorderTraversalToList(proot);

    if (tree.size() 1) return -1;

    return tree.get(k - 1);

}

public static ArrayListInteger> inorderTraversalToList(TreeNode root) {

    ArrayListInteger> result = new ArrayList();

    inorderTraversal(root, result);

    return result;

}

private static void inorderTraversal(TreeNode root, ArrayListInteger> result) {

    if (root == null) {

        return;

    }

    // 中序遍历左子树

    inorderTraversal(root.left, result);

    // 处理当前节点

    result.add(root.val);

    // 中序遍历右子树

    inorderTraversal(root.right, result);

}

public class Solution {
    public int KthNode (TreeNode proot, int k) {
        if (proot == null || k == 0) return -1;
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(proot);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        Collections.sort(list);
        if(k > list.size()) return -1;
        return list.get(k - 1);
    }
}

public class Solution {
    // res -- 保存返回值，count -- 统计次数（第几小）
    int res = -1, count = 0;
    public int KthNode (TreeNode proot, int k) {
        if (proot == null) return res;
        inorder(proot, k);
        return res;
    }

    public void inorder(TreeNode proot, int k) {
        // 当遍历到节点为空或者超过k时，返回
        if (proot == null || count > k) return;
        inorder(proot.left, k);
        // 判断是否是需要的第k小
        if (++count == k) res = proot.val;
        inorder(proot.right, k);
    }
}

import java.util.*;

public class Solution {

    public int KthNode (TreeNode proot, int k) {
        // write code here
        if(proot == null) {
            return -1;
        }
        ArrayList<Integer> list = sortTree(proot.left);
        if(list.size() == k - 1) {
            list.add(proot.val);
        }else if(list.size() < k - 1) {
            list.add(proot.val);
            list.addAll(sortTree(proot.right));
        }
        if(k <= 0 || k > list.size()) {
            return -1;
        }
        return list.get(k - 1);
    }
    
    public ArrayList<Integer> sortTree(TreeNode proot) {
        ArrayList<Integer> temp = new ArrayList<Integer>();
        if(proot == null) {
            return temp;
        }
        temp.addAll(sortTree(proot.left));
        temp.add(proot.val);
        temp.addAll(sortTree(proot.right));
        return temp;
    }
}

public class Solution {
    private int num = 0;
    
    public int KthNode (TreeNode proot, int k) {
        if (proot == null) {
            return -1;
        }
        this.num = k;
        int result = KthNode(proot.left, k);
        if (result != -1) {
            return result;
        }
        if (--this.num == 0) {
            return proot.val;
        }
        return this.KthNode(proot.right, this.num);
    }
}

public int KthNode (TreeNode proot, int k) {
        // write code here
        int[] ans = f(proot, k);
        if (ans[0] == 1)
            return ans[1];
        return -1;
    }
 
    public int[] f(TreeNode proot, int k) {
        if (proot == null)
            return new int[]{0,0,0};
        int[] left = f(proot.left, k);
        if (left[0] == 1)
            return left;
        if (left[2] == k-1)
            return new int[]{1,proot.val,0};
        int[] right = f(proot.right, k - left[2] - 1);
        if (right[0] == 1)
            return right;
        return new int[]{0,0,left[2]+1+right[2]};
    }