剑指offer----二叉搜索树的后序遍历----java实现

古城微笑少年丶 2022-09-23 08:23 32阅读 0赞

一、

二叉搜索树，又叫二叉排序树，简称BST

二叉排序树或者是一棵空树，或者是一棵具有下列特性的非空二叉树：

（1）若左子树为空，则左子树上所有的节点关键字均小于根节点的关键字；

（2）若右子树非空，则右子树上所有的节点的关键字均大于根节点的关键字；

（3）左右子树本身也是一棵二叉排序树。

后序遍历的顺序： 左 右 根

一般在处理二叉树的遍历顺序时，先找到根节点，根据根节点把序列拆分为左子树对应的子序列和右子树对应的子序列。接下来再用递归处理左右子树。

对于后序遍历遍历数组，数组的最后一个元素是整个树的根节点。最后一个元素之前的数组，可以分为两个部分：

第一部分是左子树的后序遍历序列，它们的值都比根节点小；

第二部分是右子树的后序遍历序列，它们的值都比根节点大；

此题先根据给定的后序数组找到树的根节点，

（1）与左子树中的节点对比：从数组的开头一一与根节点进行比较，当数组中的元素比根节点大时，跳出当前循环；

（2）与右子树中的节点对比：从上一步跳出的那个节点开始直到数组的倒数第二个元素，如果其中有比根元素小的元素，则返回false;

利用递归再去判断左右子树是否全为二叉排序树

public boolean VerifySquenceOfBST(int [] sequence) 
    	    {
    	        
    		        if (sequence.length <= 0)
    		        {
    		        	return false;
    		        }
    		        else
    		        {
    		        	return compare(sequence,0,sequence.length-1);
    		        }
    		    
    	    }
    	 private boolean compare(int[]a,int start,int end)
    	 {
    		 if(start == end)//数组中只有一个元素，直接返回true
    		 { return true;}
    		 
    		 int i = start;
    		while(a[i++] < a[end] && i < end);//从数组开始位置开始比较，若是比根节点大，则停止遍历比较
    		
    		 int j = i;//右子树的第一个节点在数组中的索引
    		 while(a[j++] > a[end] && j < end);//从比根元素大的第一个元素开始比较，直到数组的倒数第二个元素
    		 
    		 if(j < end)//若j不是数组的最后一个索引，则不是二叉搜索树
    			 return false;
    		 if(i == start || i == end)//若只有右子树或者只有左子树，数组除最后一个元素外都是其左孩子或者右孩子
    			 return compare(a,start,end-1);
    		 else  //左右子树都不为空，递归判断左右子树是否全为搜索二叉树
    			 return (compare(a,start,i-1)&&compare(a,i,end-1));			 
    	 }