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

参考题解大佬的

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.Stack;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
        //把每一道题都当做面试时的题目来做，充分发挥自我思考的能力
        if(pRoot == null || k <=0){
            return null;
        }
        //因为栈刚好是先入后出的数据额结构，所以倒数第K小的，就是出栈时第K个元素
        Stack<TreeNode> stack = new Stack<>();//建立栈
        TreeNode cur = pRoot;
        //while部分为中序遍历
        while(!stack.isEmpty() || cur != null){
            if(cur != null){
                //当前节点不为null,应该寻找左节点
                stack.push(cur);
                cur = cur.left;
            }else{
                //当前节点为null，证明到了最左边的叶子节点了
                //这里有一个共识是，最小的值一定是在最左边的叶子节点上上的
                //则弹出栈内元素，相当于按顺序输出最小值
                cur = stack.pop();
                //计数器功能
                k--;
                if(k == 0){
                    return cur;
                }
                cur = cur.right;
            }
        }
        return null;
    }


}