题解 | #二叉搜索树的第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

        //遍历，然后升序放入一个集合或者数组，取出第k-1个元素，肯定是可行的，但是这就完全没有利用搜索二叉树的特性了，不是最优解

        //分析搜索二叉树，最小节点，肯定是二叉树的最左叶子节点，然后是它的父节点，然后是它的右节点，
        
        //然后看父节点，又是一样的情况，父节点如果是

        //但是这里有个问题，我们没有指向父节点的额外指针，所以只能从根节点往下遍历。

        //如果遍历的同时，有一个指针记录着，落后的那个点，是不是就可以达到

        //前序遍历是(根-左-右边)、中序(左-根-右)、后序(左-右-根)

        //假如我们按照中序遍历，一定是从小到大取出这颗搜索二叉树。

        //那么这道题就转化为了，用中序遍历，取出第K个节点。

        int count = 0;

        TreeNode tempNode = proot;
        Stack<TreeNode> stack = new Stack<>();
        
        //进行中序遍历
        while(tempNode != null || !stack.isEmpty()){

            while(tempNode != null){
                stack.push(tempNode);
                tempNode = tempNode.left;
            }
            //遍历完左子树，开始遍历右子树

            tempNode = stack.pop();

            /** 这一段，是本题的求解 */
            count++;
            if(count == k){
                return tempNode.val;
            }
            /** 这一段，是本题的求解 */


            System.out.println("中序遍历，打印二叉树节点:" + tempNode.val);

            //最后，遍历右子树
            tempNode = tempNode.right;
        }
    

        return -1;
    }
}