本文共 1738 字，大约阅读时间需要 5 分钟。
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \ 6 10 / \ / \ 5 7 9 11因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
分析：这是一道trilogy的笔试题，主要考查对二元查找树的理解。
在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于根结点开始到根结点前 面的一个元素为止，所有元素都应该大于根结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右 两部分是不是都是二元查找树。
在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：第一部分是左子树结点的值，他们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。 |
参考代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | using namespace std; /// // Verify whether a squence of integers are the post order traversal // of a binary search tree (BST) // Input: squence - the squence of integers // length - the length of squence // Return: return ture if the squence is traversal result of a BST, // otherwise, return false /// bool verifySquenceOfBST( int squence[], int length) { if (squence == NULL || length <= 0) return false ; // root of a BST is at the end of post order traversal squence int root = squence[length - 1]; // the nodes in left sub-tree are less than the root int i = 0; for (; i < length - 1; ++ i) { if (squence[i] > root) break ; } // the nodes in the right sub-tree are greater than the root int j = i; for (; j < length - 1; ++ j) { if (squence[j] < root) return false ; } // verify whether the left sub-tree is a BST bool left = true ; if (i > 0) left = verifySquenceOfBST(squence, i); // verify whether the right sub-tree is a BST bool right = true ; if (i < length - 1) right = verifySquenceOfBST(squence + i, length - i - 1); return (left && right); } |