一,问题介绍
近来接触了不少关于二叉树的递归操作的题目,对递归又有了更深一步的理解。这篇文章要解决的问题是:
给出一个序列,判断该序列是否为二叉树查找树的后序遍历序列。我们知道:二叉树查找树中序遍历是有序的。也就是说,给定了后序遍历序列,其实就知道了中序遍历序列。因为,把后序遍历序列排序就得到了中序遍历序列。
又因为,中序遍历序列 和 后序遍历序列可以唯一确定一棵二叉树,故:给定一个序列,从理论上就证明了:可以判断该序列是否是二叉查找树的后序遍历序列。
这里,还是用递归的方式进行判断,这种递归思路和 中的 isSubTree 递归方法 的 递归原理是一样的!
二,算法分析
要求解这个问题,需要对二叉树的遍历顺序的性质有一定的了解。
对于二叉树的先序遍历序列,第一个元素是根结点,后面剩余的元素分为连续的两部分:前面的一部分是根的左子树中的结点元素,后面的另一部分是根的右子树中的结点元素。
对于二叉树的后序遍历,最后一个元素是根结点,后面剩余的元素分为连续的两部分:前面的一部分是根的左子树中的结点元素,后面的另一部分是根的右子树中的结点元素。嗯,没错,就是 前面的一部分是根的左子树中的结点元素,后面的另一部分是根的右子树中的结点元素.因为,后序遍历就是先访问根的左子树啊,再访问根的右子树啊,最后再访问根结点啊。举例如下:
这棵二叉查找树的后序遍历序列如下: 5,7,6,9,11,10,8
①看,最后一个元素是根。前面连续的部分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 }