建站公司 网站/河南靠谱seo电话

思路

什么是二叉搜索树

可以看出，在二叉树中：

• 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

题目是判断一个序列是不是某二叉搜索树的合法的后序遍历序列
递归 + 树的后序遍历模拟

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。
数据范围

数组长度 [0,1000]

。
样例

输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

java代码

class Solution {private int [] seq;public boolean 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)  // 右边应该都比root大return false;// 递归处理左右两边return dfs(l, k - 1) && dfs(k, r - 1);}public boolean verifySequenceOfBST(int [] sequence) {seq = sequence;return dfs(0, seq.length -1);}
}