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

import java.util.*;

/*
 * 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) {
        // write code here

        //最容易想到的方法就是把二叉树遍历出来，并把节点值按升序放入一个集合或数组

        //但是这样就完全没有用到二叉搜索树的特性了。

        //根据性质，我们知道二叉搜索树的最小的节点，一定是最左的叶子节点！


        //我们使用中序遍历(左-根--右),就可以拿到二叉搜索树的从小到大的节点集合。
        int count = 0;
        
        //使用栈，进行中序遍历
        Stack<TreeNode> stack = new Stack();
        TreeNode tempNode = proot;
        while(tempNode != null || !stack.isEmpty()){
            while(tempNode != null){
                stack.push(tempNode);
                tempNode = tempNode.left;
            }
            tempNode = stack.pop();
            count++;
            if(count == k){
                return  tempNode.val;
            }
            //遍历完左节点，拿到根节点后，开始拿右节点
            tempNode = tempNode.right;
        }

        return -1;
    }
}