The kth smallest node in the print binary search tree of offer

Title Overview

Given a binary search tree , Please find out the No k Small node .

Their thinking

At first I didn't notice Binary search tree The word , I still think it's an ordinary binary tree , So I did what I thought , Put the nodes of the binary tree into an array .

My idea of solving problems

Because at first I didn't notice Binary search tree The concept , So my idea is based on the ordinary binary tree search , The specific ideas are as follows ：

1. First, judge whether the current node is empty ,k Is less than 0. If it is true , Is returned null
2. Create a new length of k An array , This array will follow Node Of val Sort , The sort function is moveArr
3. moveArr The function defines that the nodes are sorted according to the idea of direct insertion sort .
4. Then recursively put the nodes of the binary tree into the array , Returns the last element in the array, that is k Small elements

The official answer to the question

When I finish my algorithm and pass it , When I looked at the solution again, I found , I'm still careless , There is no implied meaning given in the title . Binary search tree It's a very special binary tree , When both the left and right subtrees of a node exist , The values in the left subtree are all smaller than the node , All values in the right subtree are greater than the node .
The middle order traversal of binary search tree is an array sorted in ascending order , So find number one k Small nodes , Just look up the index in the array as k-1 The node of .
But the middle order traversal is to find all the nodes , But we just need to find number one k Small nodes can be , So we have some improvements to the algorithm , Use non recursive traversal in the middle order , Find No k Just jump out of the loop .

Specific ideas ：

1. First, judge whether the current node is empty ,k Is less than 0. If it is true , Is returned null
2. There will be a new Stack Stack , It is used to store the nodes in the process of traversing the middle order .
3. Will perform while Loop until the node is null And stack Stop when it's empty .

• During the cycle , Judge whether the node is empty , If it's not empty , Add the node to the stack , And point the pointer to the left child of the node ;
• If it is empty, it will node Point to the node thrown by the stack , And then the counter ++; Judge whether to find the first k Elements , Return if found , If not, point the node pointer to the right child of the current node .

Code implementation

The node tree of the function ：

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

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

    }

Use array storage

 TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k < 1) return null;
        //  See this problem , The first way I think of it is , Put the tree into an array , Then the array is judged , Return to the minimum value 
        //  First, create a new one k Bit size array , Then traverse the binary tree in turn , Insert a number into the array 
        TreeNode[] arr = new TreeNode[k];
        addTreeNode(pRoot, arr);
        return arr[k-1];
    }
    
    //  Traversal adds a number of nodes to the array 
    public void addTreeNode(TreeNode node, TreeNode[] arr){
        if(node == null) return;
        moveArr(node, arr);
        if(node.left != null) addTreeNode(node.left, arr);
        if(node.right != null) addTreeNode(node.right, arr);
    }
    
    //  Array shift ,  Determine which array is smaller than 
    public void moveArr(TreeNode node, TreeNode[] arr){
        if(node == null) return;
        for(int i=0; i<arr.length; i++){
            if(arr[i] == null){
                arr[i] = node;
                return;
            }else if(node.val < arr[i].val){
                for(int j = arr.length-1; j > i; j--){
                    arr[j] = arr[j-1];
                }
                arr[i] = node;
                return;
            }
        }
    }

Using the middle order traversal search method

 TreeNode KthNode(TreeNode pRoot, int k){
         //  At first, I didn't look at the problem carefully , If you look at the problem carefully and are very familiar with binary trees , It should have been noticed in the first place   Binary search tree   This word 
         // , The value in the left subtree of a node in the binary search tree should be less than that node , The values in the right subtree should be greater than the node 
         if(pRoot == null || k < 1) return null;
         //  The order traversal of the binary tree can find the order of the node , Just find number one k You can find the node you are looking for in the problem 
         //  Non recursive methods need to use Stack To store the parent node 
         TreeNode node = pRoot;
         Stack<TreeNode> stack = new Stack<>();
         int count = 0;
         while(node != null || !stack.isEmpty()){
             if(node != null){
                 stack.push(node);
                 node = node.left;
             }else{
                 node = stack.pop();
                 count ++;
                 if(count == k) return node;
                 node = node.right;
             }
         }
         return null;
         
     }