Leetcode——230. 二叉搜索树中第K小的元素

230. 二叉搜索树中第K小的元素

题目**

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
   3
  / 
 1   4
  
   2
输出: 1

示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / 
     3   6
    / 
   2   4
  /
 1
输出: 3

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

二叉树数据结构（题目给出）**

Definition for a binary tree node.
 
 public class TreeNode {
          
   
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {
          
   }
     TreeNode(int val) {
          
    this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
          
   
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

1、递归**

思想**

计算左子树结点个数numL 如果numL+1等于k，说明根结点第k小元素，直接返回 如果numL大于等于K，第k小元素在左子树，递归查找 否则，第k小元素在右子树，递归查找

代码**

class Solution {
          
   
    public int kthSmallest(TreeNode root, int k) {
          
   
        int numL = countNode(root.left);//计算左子树结点数
        if(numL + 1== k){
          
   //如果根结点数值第k小，直接返回
            return root.val;
        }
        //递归
        else if(k <= numL){
          
   //如果第k小元素在左子树中
            return kthSmallest(root.left, k);
        }
        else{
          
   //否则在右子树中
            return kthSmallest(root.right, k - numL - 1);
        }
    }
    public int countNode(TreeNode root) {
          
   
        if(root == null){
          
   
            return 0;
        }
        return countNode(root.left) + countNode(root.right) + 1;
    }
}

2、中序数组法**

思想**

利用二叉搜索树的中序序列有序将其转换为有序数组，然后直接返回下标k-1处元素即可

代码**

class Solution {
          
   
    public int kthSmallest(TreeNode root, int k) {
          
   
        ArrayList<Integer> arr = new ArrayList<Integer> ();
        inOrder(root, arr);
        return arr.get(k-1);//注意不可以用arr[k-1]
    //    return arr.get(k-1);//E	get(int index),Returns the element at the specified position in this list.
    }
    public ArrayList inOrder(TreeNode root, ArrayList<Integer> arr) {
          
   //将二叉搜索树进行中序遍历转换成有序数组
        if(root == null){
          
   
            return arr;
        }
        inOrder(root.left, arr);
        arr.add(root.val);
        inOrder(root.right, arr);
        return arr;
    }
}

3、中序栈法**

思想**

利用二叉搜索树的中序序列有序，先将所有的左孩子入栈，遍历到最小值，之后依次弹出最小值，如果有右孩子也要遍历，直到找到第k个弹出元素即可

代码**

class Solution {
          
   
    public int kthSmallest(TreeNode root, int k) {
          
   
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();//用法没搞懂
    //    Stack<TreeNode> stack = new Stack<TreeNode> ();
        while(true){
          
   
            while(root != null){
          
   
                stack.add(root);
                root = root.left;
            }
            root = stack.removeLast();
            k--;
            if(k == 0){
          
   
                return root.val;
            }
            root = root.right;
        }
    }
}

问题

LinkedList stack = new LinkedList();//用法没搞懂 stack.add(root); root = stack.removeLast();