二叉搜索树的第k个节点

解法一：

public class Solution {
    ArrayList<TreeNode> list = new ArrayList<>(); // (1)
    TreeNode KthNode(TreeNode pRoot, int k) {
        addNode(pRoot);
        if (k >= 1 && list.size() >= k) {
            return list.get(k - 1);
        }
        return null;
    }
    // 中序遍历
    void addNode(TreeNode cur) {   // (2)
        if (cur != null) {
            addNode(cur.left);
            list.add(cur);
            addNode(cur.right);
        }
    }
}

解法二：

public class Solution {
 TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k <= 0){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>(); //建立栈
        TreeNode cur = pRoot;
//while 部分为中序遍历
        while(!stack.isEmpty() || cur != null){ 
            if(cur != null){
                stack.push(cur); //当前节点不为null，应该寻找左儿子
                cur = cur.left;
            }else{
                cur = stack.pop();//当前节点null则弹出栈内元素，相当于按顺序输出最小值。
                if(--k <= 0){ //计数器功能
                    return cur;
                }
                cur = cur.right;
            }
        }
        return null;
    }
}