JZ62 二叉搜索树的第k个节点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

递归迭代都可以。递归21秒，迭代28秒。

先上递归

public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k){
        if(k<=0) return null;
        this.k=k;
        this.count=0;
        inorder(pRoot);
        return ans;
    }
    int k, count; TreeNode ans;
    void inorder(TreeNode root){
        if(root==null||ans!=null) return;
        inorder(root.left);
        count++;
        if(k==count) ans=root;
        inorder(root.right);
    }
}

再上迭代

import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k){
        if(k<=0) return null;
        TreeNode curr=pRoot;
        Deque<TreeNode> stack=new ArrayDeque<>();
        int count=0;
        while(!stack.isEmpty()||curr!=null){
            while(curr!=null){
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop(); count++;
            if(count==k) return curr;
            curr=curr.right;
        }
        return null;
    }
}