题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true，否则返回false。
假设输入的数组的任意两个数字都互不相同。
数据范围
数组长度 [0,1000]。
样例
输入：[4, 8, 6, 12, 16, 14, 10] 输出：true
方法一：dfs O(n)
这道题根据后序遍历的性质进行 dfs 操作：
后序遍历数组的最后一个数为根结点。
从数组 l 的位置开始往后遍历，直至超过 r 或找到大于根结点第一个数。
如果有大于第一个根结点数，则判断该数到根结点之间的数是否都是大于根结点的，如果不是则输出 false 。
继续遍历根结点的左子树和右子树。
我们拿题目样例举例，看看具体是如何实现的：
第一步： 将数组的最后一个结点作为根结点，从 0 开始往后遍历，发现第一个大于根结点的元素 12 ，并且其后面到根结点的元素都要比根结点大，故满足要求，继续往根结点左右结点递归。
第二步： 分别将最后一个元素 6 和 14 作为根结点，然后重复第一步操作，发现都满足要求，继续往后递归。
第三步： 发现都已经递归到叶子结点，并且都满足要求，故最终返回 true 。
class Solution { public: vector<int> seq; bool dfs(int l, int r) { if (l >= r) return true; int root = seq[r]; //找到第一大于根节的数 int k = l; while (k < r && seq[k] < root) k++; //判断第一个大于根结点的数到根结点之间的数是否都大于根结点 for (int i = k; i < r; i++) if (seq[i] < root) return false; return dfs(l, k - 1) && dfs(k, r - 1); //继续遍历左右子树 } bool verifySequenceOfBST(vector<int> sequence) { seq = sequence; return dfs(0, sequence.size() - 1); } };
欢迎大家在评论区交流~
