二叉搜索树的第k个节点

给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。

二叉搜索树是右节点的val比左节点的val大。

关于·二叉树的题目，首先肯定会想到递归方法，所以递归写法就是：

import java.util.*;
public class Solution {
    ArrayList<TreeNode> list=new ArrayList<>();
   //这里写一个中序遍历的方法，将整个树通过递归放入list中
    void addNode(TreeNode cur){
        if(cur!=null){
                addNode(cur.left);
            list.add(cur);
            addNode(cur.right);
        }
    }
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot==null||k<=0) return null;
        addNode(pRoot);
        //将树放入list中
       if(k>0&&list.size()>=k){
       //直接获取k-1个元素，因为list是从0开始的，所以第k小就是k-1个
            return list.get(k-1);
            
       }
        return null;
    }
 
 
}

           

非递归的方法：

import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot==null||k<=0) return null;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=pRoot;
        while(!stack.isEmpty()||cur!=null){
            if(cur!=null){
            //前序遍历，将树的节点放入栈中
                stack.push(cur);
                cur=cur.left;
            }else{
            //cur为null就去放他的右节点
                cur=stack.pop();
                 
                if(--k==0){//计数，弹出第k个就是我们所需要的节点
                    return cur;
                }
                cur=cur.right;
            }
        }
        return null;
    }
 
 
}