[leetcode] day90 the element with the smallest K in the binary search tree

subject

230. Binary search tree K Small elements 【 secondary 】

Answer key

In the sequence traversal

The order traversal in a binary search tree is a sequence of increasing numbers , So the first K The small element is the second element in the binary search tree K The value of nodes , Using the middle order traversal can solve ~

class Solution {
    
    int count=0,res=0;
    public int kthSmallest(TreeNode root, int k) {
    
        midOrder(root,k);
        return res;
    }
    public void midOrder(TreeNode root,int k){
    
        if(root==null)
            return;
        midOrder(root.left,k);
        count++;
        if(count==k){
    
            res=root.val;
            return;
        }
        midOrder(root.right,k);
    }
}

Time complexity ：$O(n)$

Spatial complexity ：$O(1)$

p.s The term is finally over ！ There will be no classes in the future ！ But the efficiency at home is hard to say , also 5 It's getting worse , If I were in school, I would have broken through 100 days