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

2020-11-09 22:41:03 Long Tao

# 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];
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);
}

//  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;
}
}
}
``````
`````` 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;

}
``````