二叉搜索树的第k个结点

题目

给定一棵结点数为 n 二叉搜索树，请找出其中的第 k 小的TreeNode结点。 数据范围： 0≤n<=100，0≤k≤100，树上每个结点的值满足0≤val≤100 要求：空间复杂度 O(1)，时间复杂度 O(n)

思路

二叉搜索树，是指一棵空树或者具有下列性质的二叉树：

1、若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2、若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

3、任意节点的左，右子树也分别为二叉搜索树；

4、没有键值相等的节点。

使用中序遍历，将每个结点存进一个list集合中，此时的集合中每个结点已经是按照val值从小到大的顺序依次排序了。只要k符合范围，那么取出k-1的结点就是返回的结果。

本题的思路是参照他人的题解。

代码

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    ArrayList<TreeNode> res=new ArrayList();
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot==null){
            return null;
        }
        
        preOrder(pRoot);
        TreeNode result=null;
        //如果k合法
        if(k-1>=0 && k-1<res.size()){
           result=res.get(k-1);
        }
        return result;
    }
    
    //中序遍历二叉搜索树
    void preOrder(TreeNode pRoot){
        if (pRoot != null){
            preOrder(pRoot.left);
            res.add(pRoot);
            preOrder(pRoot.right);
        }
    }
//     Deque<TreeNode> preOrder(TreeNode pRoot){
//         Deque<TreeNode> d = new ArrayDeque<>();
//         if (pRoot != null){
//             d.addLast(pRoot);
//             preOrder(pRoot.left);
//             preOrder(pRoot.right);
//         }
//         return d;
//     }
}