题解 | 二叉搜索树的第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整型
     */
    // //思路1：递归中序遍历
    // //定义全局变量
    // private int count=0;
    // private int result=-1;
    // public int KthNode (TreeNode proot, int k) {
    //     // write code here
    //     if(k==0) return -1;
    //     dfs(proot,k);
    //     return result;
    // }
    // //写一个递归的函数
    // public void dfs(TreeNode root,int k){
    //     if(root==null) return;
    //     dfs(root.left,k);
    //     count++;
    //     if(count==k){
    //         result = root.val;
    //         return;
    //     }
    //     dfs(root.right,k);
    // }

    //思路2：非递归的中序遍历，需要用到栈
    public int KthNode (TreeNode proot, int k) {
        // write code here
        //边界条件判断
        if(proot==null||k==0) return -1;
        int count = 0;
        //定义栈
        Deque<TreeNode> stack = new LinkedList<>();
        //循环条件，当节点没有访问到头，或者访问到头了但是栈中还有元素没有弹出来
        while(proot!=null || !stack.isEmpty()){
            while(proot!=null){
                //当访问的节点还有，就继续访问左子树，并将节点放入栈中————左
                stack.push(proot);
                proot = proot.left;
            }
            //弹出栈顶元素，count++————中
            TreeNode temp = stack.pop();
            count++;
            if(count==k) return temp.val;
            //再访问弹出的栈顶元素的右子树，其实也是一个左中右的遍历过程————右
            proot = temp.right;
        }
        return -1;
    }
}