分享程序员开发的那些事...
更新时间：2022-09-11 17:19:07
一，问题介绍
近来接触了不少关于二叉树的递归操作的题目，对递归又有了更深一步的理解。这篇文章要解决的问题是：
给出一个序列，判断该序列是否为二叉树查找树的后序遍历序列。我们知道：二叉树查找树中序遍历是有序的。也就是说，给定了后序遍历序列，其实就知道了中序遍历序列。因为，把后序遍历序列排序就得到了中序遍历序列。
又因为，中序遍历序列 和 后序遍历序列可以唯一确定一棵二叉树，故：给定一个序列，从理论上就证明了：可以判断该序列是否是二叉查找树的后序遍历序列。
这里，还是用递归的方式进行判断，这种递归思路和 比较两棵二叉树--（比较两棵二叉树是否相同/判断一棵二叉树是否是另一棵二叉树的子树） 中的 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 else 10 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 root 20 if(sequence[rightPos] < root) 21 return false;//右子树中比根结点还小的结点 22 23 boolean leftSequence = true;//只能初始化为true 24 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 else 17 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 root 27 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 }