题解 | #二叉搜索树的第k个节点#

由于是二叉搜索树，采用中序遍历得到的第k个节点即第k小的值，判断输出是否是第k个就可以返回值了，使用栈来辅助遍历

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    public int KthNode (TreeNode proot, int k) {
        if(proot == null)    return -1;
        //中序遍历，第k个节点
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(proot);
        TreeNode node = proot;
        int i = 0;
        while(!stack.isEmpty()){
            //遍历node下的所有左节点
            while(node.left != null){
                stack.push(node.left);
                node = node.left;
            }
            i++;
            if(i == k)    return stack.pop().val;
            TreeNode tmp = stack.pop();
            //加入右子树
            if(tmp.right != null){
                stack.push(tmp.right);
                node = tmp.right;
            }
        }
        return -1;
    }
}

也可以使用递归的方法

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    int count = 0;    //标记遍历的节点数
    int result = -1;
    public int KthNode (TreeNode proot, int k) {
        if(proot == null || k <= 0)    return -1;
        KthNode(proot.left,k);
        ++count;
        if(count == k)    return result = proot.val;
        KthNode(proot.right,k);
        return result;
    }
}