剑指Offer - PHP二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。
示例
输入：
[4,8,6,12,16,14,10]
输出：
true
分析
二叉搜索树的后序遍历序列的特点：
例如，后序遍历序列：4,8,6,12,16,14,10
- 根节点：序列最后一个元素，即
10- 左子树：都比根节点小，即
4,8,6- 右子树：都比根节点大，即
12,16,14
- 找出序列的左、右子树
- 递归左、右子树，判断是否符合二叉树搜索树后序遍历的特点
代码
/**
* 判断序列是否为二叉搜索树遍历的结果
* @param array $sequence 序列
*/
function VerifySquenceOfBST($sequence)
{
$length = count($sequence); // 序列长度
if ($length == 0) return false;
$root = end($sequence); // 序列的根节点
// 找到第一个大于根节点的位置，区分出左、右子树
for ($i = 0; $i < $length - 1; $i++)
if ($sequence[$i] > $root) break;
// 验证右子树是否都大于根节点
for ($j = $i + 1; $j < $length - 1; $j++)
if ($sequence[$j] < $root) return false;
$left = $right = true;
if ($i > 0) { // 有左子树，递归
$left = VerifySquenceOfBST(array_slice($sequence, 0, $i));
}
if ($j < $length) { // 有右子树，递归
$right = VerifySquenceOfBST(array_slice($sequence, $i, $length - $i - 1));
}
return $left && $right;
}
关于 LearnKu
粤公网安备 44030502004330号