二叉搜尋樹的第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;
    }
 
 
}