首页 > 代码库 > 判断序列是否是二叉树的后序遍历序列

判断序列是否是二叉树的后序遍历序列

2024-07-09 05:27:38   220人阅读

　　这个题的意思就是给定一个序列，判断这个序列是否是某个二叉排序树的后序遍历序列，这个算法的方法主要是根据后序遍历的性质，首先这个序列的最后一个元素肯定是根元素，然后将序列从左往右遍历，找到第一个大于根元素的点，这个点左边的肯定是当前根的左子树，这个点的右边肯定是当前根的右子树，继续向后遍历，看右子树中是否有值小于根，如果有，则false，否则分左右子树分别再次调用函数进行判断。具体代码如下：

 1 public class IsLastOrder{ 2  3     public boolean islast(int [] array,int start,int end){ 4         boolean left = true; 5         boolean right = true; 6         if(start>end){ 7             return false; 8         } 9         if(start==end){10             return true;11         }12 13         int root = array[end];14         int index = -1;15         for(int i=start;i<end;i++){16             if(array[i]>root){17                 index = i;18                 break;19             }20         }21         for(int i=index;i<end;i++){22             if(array[i]<root){23                 return false;24             }25         }26         if(index>0){27             left = islast(array,start,index-1);28         }29         if(index<end-1){30             right = islast(array,index,end-1);31         }32         return left&&right;33     }34 35     public static void main(String [] args){36         int [] array = {7,4,6,5};37         IsLastOrder ilo = new IsLastOrder();38         System.out.println(ilo.islast(array,0,3));39     }40 }

 


联系
我们