Post order traversal sequence of 24 binary search tree of sword finger offer

Title Description

• Enter an array of integers , Determine whether the array is the result of the subsequent traversal of a binary search tree .
• If so, return ture, Otherwise return to false.
• Suppose that any two numbers of the input array are different from each other .

analysis

• Find the root node
• Ab initio traversal sequence , The first element larger than the root node is the starting point of the right subtree
• Determine whether the right subtree is larger than the root node , If not return false, if , Go to the next step
• Judge the left subtree and the right subtree according to the above rules , If the left and right subtrees can return true, Then the whole sequence is the post order traversal sequence of the binary search tree , return true

Code implementation

public boolean verifySquenceOfBST(int [] sequence) {
    
    
	if(sequence == null || sequence.length == 0){
    
		return false;
	}
	
	int len = sequence.length;
	int root = sequence[len - 1];
	
	int i = 0;
	for(; i < len - 1; i++){
    
		if(sequence[i] > root){
    
			break;
		}
	}
	
	int j = i;
	for(;j < len - 1; j++){
    
		if(sequence[j] < root){
    
			return false;
		}
	}
	
	boolean left = true;
	boolean right = true;
	if(i > 0){
    
		left = verifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
	}
	if(i < len - 1){
    
		right = verifySquenceOfBST(Arrays.copyOfRange(sequence,i,len - 1));
	}
	
	return left && right;
}



<p></p>