题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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;
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10066732.html
