博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
给定一个序列,判断该序列是否为二叉树查找树的后序遍历序列
阅读量:5080 次
发布时间:2019-06-12

本文共 4434 字,大约阅读时间需要 14 分钟。

一,问题介绍

近来接触了不少关于二叉树的递归操作的题目,对递归又有了更深一步的理解。这篇文章要解决的问题是:

给出一个序列,判断该序列是否为二叉树查找树的后序遍历序列。我们知道:二叉树查找树中序遍历是有序的。也就是说,给定了后序遍历序列,其实就知道了中序遍历序列。因为,把后序遍历序列排序就得到了中序遍历序列。

又因为,中序遍历序列 和 后序遍历序列可以唯一确定一棵二叉树,故:给定一个序列,从理论上就证明了:可以判断该序列是否是二叉查找树的后序遍历序列。

这里,还是用递归的方式进行判断,这种递归思路和 中的 isSubTree 递归方法 的 递归原理是一样的!

 

二,算法分析

要求解这个问题,需要对二叉树的遍历顺序的性质有一定的了解。

对于二叉树的先序遍历序列,第一个元素是根结点,后面剩余的元素分为连续的两部分:前面的一部分是根的左子树中的结点元素,后面的另一部分是根的右子树中的结点元素。

对于二叉树的后序遍历,最后一个元素是根结点,后面剩余的元素分为连续的两部分:前面的一部分是根的左子树中的结点元素,后面的另一部分是根的右子树中的结点元素。嗯,没错,就是 前面的一部分是根的左子树中的结点元素,后面的另一部分是根的右子树中的结点元素.因为,后序遍历就是先访问根的左子树啊,再访问根的右子树啊,最后再访问根结点啊。举例如下:

这棵二叉查找树的后序遍历序列如下:  5,7,69,11,108

①看,最后一个元素是根。前面连续的部分5, 6, 7 是根的左子树;后面连续的部分9,11,10 是根的右子树。

②另外,对于二叉查找树而言,还有一个性质:就是根的左子树中结点都比根小,根的右子树中的结点都比根大。

因此,基于①②这两点,就可以判断一个给定的序列是不是二叉查找树的后序遍历序列了。

1)若 右子树对应的序列中有比根小的元素,则它不是后序遍历序列; 同理左子树

2)若 相对于树根结点而言,左右子树对应的后序遍历序列满足①②,则进一步递归判断左子树和右子树对应的序列是否还满足①②.....

直到判断到叶结点为止。

1 private static boolean verifyPostSequenceOfBST(int[] sequence, int start, int end){ 2          3         int root = sequence[end]; 4          5         int left = start; 6         while(sequence[left] != root){ 7             if(sequence[left] < root) 8                 left++; 9             else10                 break;11         }12         13         /*14          * 如果上面的while循环的if一次也没有执行,第一个结点比根大,则说明没有左子树.此时left指向右子树中的第一个结点 15          * 如果上面的while循环到了根结点,while会自动结束.此时所有的孩子结点都小于根结点,说明没有右子树16          */17         18         int rightPos = left;//left指向的右子树中的第一个结点 19         for(; rightPos < end; rightPos++)//sequence[end] is root20             if(sequence[rightPos] < root)21                 return false;//右子树中比根结点还小的结点    22         23         boolean leftSequence = true;//只能初始化为true24         if(left > start)//二叉查找树有左子树25             leftSequence = verifyPostSequenceOfBST(sequence, 0, left-1);26         27         boolean rightSequence = true;28         if(left < end)//二叉查找树有右子树29             rightSequence = verifyPostSequenceOfBST(sequence, left, end-1);30         31         return leftSequence && rightSequence;32     }

这里的递归总思路就是:首先判断根的左右子树是否符合二叉查找树的规则(第18行到第21行)。若符合,则继续进一步判断左右子树是否符合二叉查找树的规则(第23行到29行)。

 

①第3行,获得当前根结点。它是后序序列中的最后一个结点

②第5行至第11行,找出序列中第一个大于根结点的结点。就是为了区分出 连续的两部分。

“对于二叉树的后序遍历,最后一个元素是根结点,后面剩余的元素分为连续的两部分:前面的一部分是根的左子树中的结点元素,后面的另一部分是根的右子树中的结点元素。

区分出这连续的两部分后,我们知道,第一部分是左子树,它都是比根小的。故在第18行至第21行判断 第二部分(右子树)中是否存在有比根还小的元素

若有,则不是后序遍历序列。(第20行if成立,返回false)

③第23行至第25行,首先判断是否有左子树,若有,则左子树的后序遍历序列也需要满足 (二:算法分析)中提到的两点。

比如说,此时的左子树的序列是: 5, 7 ,6 。因此,需要判断 5, 7 ,6 是否是后序遍历序列。类似地,最后一个元素是根,即根是6。然后,找到7比根6 大,这里又分成了两部分,故左子树是5,右子树是7......

因此,需要第25行进行递归调用。

④第27至29行,是对右子树进行递归调用,原理与③中一致。

⑤第23行和第27行的两个boolean初始化只能为true。这是因为,当递归调用到叶子结点时,递归出来的子树只有根结点了,此时这两个boolean值还未被改变,这说明该序列满足后序序列性质。故最终第31行返回true

 

三,完整代码实现

1 public class PostOrderSequence { 2      3     public static boolean verifyPostSequenceOfBST(int[] sequence){ 4         if(sequence == null || sequence.length == 0) 5             return false; 6         return verifyPostSequenceOfBST(sequence, 0, sequence.length - 1); 7     } 8     private static boolean verifyPostSequenceOfBST(int[] sequence, int start, int end){ 9         10         int root = sequence[end];11         12         int left = start;13         while(sequence[left] != root){14             if(sequence[left] < root)15                 left++;16             else17                 break;18         }19         20         /*21          * 如果上面的while循环的if一次也没有执行,第一个结点比根大,则说明没有左子树.此时left指向右子树中的第一个结点 22          * 如果上面的while循环到了根结点,while会自动结束.此时所有的孩子结点都小于根结点,说明没有右子树23          */24         25         int rightPos = left;//left指向的右子树中的第一个结点 26         for(; rightPos < end; rightPos++)//sequence[end] is root27             if(sequence[rightPos] < root)28                 return false;//右子树中比根结点还小的结点    29         30         boolean leftSequence = true;31         if(left > start)//二叉查找树有左子树32             leftSequence = verifyPostSequenceOfBST(sequence, 0, left-1);33         34         boolean rightSequence = true;35         if(left < end)//二叉查找树有右子树36             rightSequence = verifyPostSequenceOfBST(sequence, left, end-1);37         38         return leftSequence && rightSequence;39     }40     41     public static void main(String[] args) {42         int[] sequence = {5,7,6,9,11,10,8};43         System.out.println(verifyPostSequenceOfBST(sequence));44         int[] sequence2 = {1,2,3};45         System.out.println(verifyPostSequenceOfBST(sequence2));46     }47     48 }

 

转载于:https://www.cnblogs.com/hapjin/p/5561870.html

你可能感兴趣的文章
黑马程序员——2 注释
查看>>
用OGRE1.74搭建游戏框架(三)--加入人物控制和场景
查看>>
转化课-计算机基础及上网过程
查看>>
android dialog使用自定义布局 设置窗体大小位置
查看>>
ionic2+ 基础
查看>>
互联网模式下我们更加应该“专注”
查看>>
myeclipse集成jdk、tomcat8、maven、svn
查看>>
查询消除重复行
查看>>
Win 10 文件浏览器无法打开
查看>>
HDU 1212 Big Number(C++ 大数取模)(java 大数类运用)
查看>>
-bash: xx: command not found 在有yum源情况下处理
查看>>
[leetcode]Minimum Path Sum
查看>>
内存管理 浅析 内存管理/内存优化技巧
查看>>
hiho1079 线段树区间改动离散化
查看>>
【BZOJ 5222】[Lydsy2017省队十连测]怪题
查看>>
第二次作业
查看>>
【input】 失去焦点时 显示默认值 focus blur ★★★★★
查看>>
Java跟Javac,package与import
查看>>
day-12 python实现简单线性回归和多元线性回归算法
查看>>
Json格式的字符串转换为正常显示的日期格式
查看>>