230. The k-th smallest element in the binary search tree

1、 Title Description

2、 Topic analysis

To find the binary search tree, sort in k The location of the elements , Equivalent to the need to search the binary tree 【 Ascending 】 Sort .

That is, the corresponding transformation is to transform the binary search tree , Convert to 【 Middle preface 】 Traverse , And stored in a container , It can be list, Array , Or hash table , Queues are OK .

Then get page k A place , For example, I use list, index Subscript from 0 Start , So the first k Elements , That is, get the subscript k-1 The elements of ,list.get(k-1); The code is as follows ：

class Solution {
    // The binary tree is traversed in middle order 
     List<Integer> list = new ArrayList<Integer>();
    public int kthSmallest(TreeNode root, int k) {
       if(root == null) return -1;
       // here list In ascending order 
       dfs(root);
       if(list.size() >= k)
           return list.get(k-1);
       return -1;
    }

    private void dfs(TreeNode root){
         if(root == null) return;
         dfs(root.left);
         list.add(root.val);
         dfs(root.right);
    }

}

Complexity analysis ：

Time complexity O(N)： In the sequence traversal , Each element is traversed to , So the complexity is O(N).
Spatial complexity O(N)：list Contains all elements , So the space complexity is zero O(N).

        On the basis of the above, optimize the time and space complexity , That is, once you get the k Elements , Stop . There is no need to traverse all to the element .

class Solution {
    int res;
    int sortK; //  After sorting to k Elements , This needs to be a global variable 
    public int kthSmallest(TreeNode root, int k) {
       //【 In the sequence traversal 】
       this.sortK = k;
       dfs(root);
       return res;
    }

    private void dfs(TreeNode root){
         if(root == null ||  sortK <= 0) return;
         dfs(root.left);
         if(--sortK == 0) res = root.val;
         dfs(root.right);
    }
}

Complexity analysis ：

Time complexity ： Make h  For the height of the tree , Reach the leaf position first （ Minimum node position ）, The complexity is O(h), And find number one k Small elements , The complexity is O(k). whole   The complexity is O(h+k)
Spatial complexity ： Make h For the height of the tree , The complexity is O(h)