The k-th node of the binary search tree [sword finger offer]

subject

Answer key

• Law 1 ：
  Store the results of the middle order traversal of the binary search tree into the array , Take the first... Of the array k results .

function KthNode(pRoot, k)
{
    
    if(!pRoot || k<1) return;
    return gotoArr(pRoot)[k-1];
}
let res = [];
function gotoArr(root){
    
    //  The middle order traversal result is stored in the array 
    if(!root) return;
    gotoArr(root.left);
    res.push(root);
    gotoArr(root.right);
    return res;
}

Existing problems ： You need to traverse all nodes , High time complexity

// 》》 Improved version 《《
let res = [];
let key; // flag： Determine whether to get the result 
function KthNode(pRoot, k)
{
    
    if(!pRoot || k<1) return;
    key = k;
    return gotoArr(pRoot)[k-1];
}

function gotoArr(root){
    
    //  The middle order traversal result is stored in the array 
    if(res.length === key) return; // Get the result , stop it 
    if(root.left) gotoArr(root.left);
    res.push(root);
    if(root.right) gotoArr(root.right);
    return res;
}

• Law two ：
  In order to traverse the binary search tree , Search to k Node time , stop it .

function KthNode(root, k)
{
    
    if(!root || k<1)return null;
    let res = null;
    //  For tracking k value , Define the middle order traversal function inside 
    function traverse(root){
    
        if(!root) return null;
        if(root.left) res = traverse(root.left);
        if(!res){
    
            //  No result found in the left subtree 
            if(k===1) res=root;
            k--;
        }
        if(root.right) res = traverse(root.right);
        return res;
    }
    return traverse(root);
}

Supplementary information ：

Binary search tree ：

a. Definition :

Binary search tree （Binary Search Tree）, Also known as a binary search tree 、 Binary search tree 、 Ordered binary tree or ordered binary tree . Meet the following conditions ：

• If its left subtree is not empty , The value of all nodes on the left subtree is less than its root node .
• If its right subtree is not empty , The value of all nodes on the right subtree is greater than its root node .
  Its left 、 The right subtree is also a binary search tree . As shown in the figure below ：
  

b. Binary search tree has efficient insertion 、 Delete 、 Query operation .

The time complexity of the average time is O(log n), The worst case scenario is O(n). Binary search tree is different from heap , It doesn't have to be a complete binary tree , The bottom layer is not easy to be directly represented by an array, so the linked list is used to realize the binary search tree .

c. Binary search process
The idea of binary search is 1946 in , Finding problems is a very important basic problem in computer , For an ordered sequence , To use binary search . If we're looking for an element , First look at the value in the middle of the array V And the size of the data you need to find , There are three situations ：

• 1、 Equal to the data you want to find , Find it directly
• 2、 If less than V, In less than V Some groups continue to query
• 2、 If more than V, In more than V Some groups continue to query

Code :

var search = function(nums, target) {
    
    let [start,end] = [0,nums.length-1];
    let middle,midItem;//  Intermediate element index and content 
    while(start<=end){
    
        middle = Math.floor((start+end)/2);
        midItem = nums[middle];
        if(midItem === target){
    
            return middle;
        }            
        else if(midItem > target){
    
            end = middle-1;
        }
        else{
    
            start = middle+1;
        }
    }
    return -1;

};

* Please quote from QW’s Blog！*