一，问题介绍

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

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

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

这里，还是用递归的方式进行判断，这种递归思路和 中的 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 }