描述

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1. 返回第k小的节点值即可
2. 不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
3. 保证n个节点的值不一样

思路1：递归

二叉搜索树中序遍历可得升序数组

public class Solution {
    int i = 0;
    int ret = -1;
    public int KthNode (TreeNode proot, int k) {
        if(proot == null || k <= 0) {
            return -1;
        }
        KthNode(proot.left, k);
        i++;
        if(i == k) {
            return ret = proot.val;
        }
        KthNode(proot.right, k);
        return ret;
    }
}

思路2：借助栈遍历

深度遍历需要借助栈：栈中记录搜索路径。先到达最左端，再向上搜索，检查是否有右节点

想象一个指针移动，+表示入栈，-表示出栈：5+、3+、2+-、3-、4+-、5-、7+、6+-、7-、8+-

public class Solution {
    public int KthNode (TreeNode proot, int k) {
        if(proot == null) {
            return -1;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(proot);
        TreeNode node = proot;
        int i = 0;
        while(!stack.isEmpty()) {
            // 先到达最左端
            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;
    }
}