[剑指offer] 23. 二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：
解法一：递归
二叉搜索树，后序遍历的数组中，最后一位是根节点，保存根节点。
除根节点外，数组中分为两部分，前一部分全部小于根节点，为左子树，另一部分全部大于根节点，为右子树。
分别找出两部分的范围，对两个子树进行递归判断是否是后序遍历序列。
class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if (sequence.empty()) return false; return helper(sequence, 0, sequence.size() - 1); } bool helper(vector<int> seq, int beg, int end) { if (beg >=end) return true; int root = seq[end]; int i = beg; while (seq[i] < root) { i++; } int j = i; while (j < end) { if (seq[j] < root) { return false; } j++; } return helper(seq, beg, i - 1) && helper(seq, i, end - 1); } };
解法二：非递归
同样的，去除数组最后一个值，也就是根，数组分为左右子树两部分。
此时数组最右边的值是右子树的根节点，大于所有左子树的值。同时，右子树部分中，所有右子树元素都大于该值。
于是判断右子树是否符合条件即可。
class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { int j = sequence.size(); if (j == 0) return false; int i = 0; while (--j) { while (sequence[i++] < sequence[j]) ; while (sequence[i++] > sequence[j]) ; if (i < j) return false; i = 0; } return true; } };