33. 二叉搜索树的后序遍历序列
1. 描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
2. 例子
示例 1:
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
3. 提示
- 数组长度 <= 1000
4. 题解
n = i_postorder.size()
时间复杂度: O($n^2$)
空间复杂度: O(n)
首先我们根据根的值可以找到树的左子树和右子树的边界，即找到左子树的最后一个值或者说右子树的第一个值。但是注意，这个过程应当是遍历而非二分查找，因为树并不一定是合法的，二分可能找到一个分界点，而该分界点前的值不都是小于根的值的，也就是说树其实是非法的。
找到分界点之后，我们就应当判断分界点后的节点值是否都是大于根节点值的，并以此判断右子树是否合法。
在判断当前树合法之后，可以递归的判断子树是否合法，并最后确定整个树的合法性。
class Solution
{
private:
bool verifyPostorder(vector<int> &i_postorder, int left, int right)
{
if(left >= right) return true;
int firstRightSubtreeIndex = left;
while(i_postorder[firstRightSubtreeIndex] < i_postorder[right])
firstRightSubtreeIndex++;
for(int i = firstRightSubtreeIndex; i < right; i++)
{
if(i_postorder[i] < i_postorder[right])
return false;
}
bool isLeftValid = verifyPostorder(i_postorder, left, firstRightSubtreeIndex - 1);
if(!isLeftValid) return false;
bool isRightValid = verifyPostorder(i_postorder, firstRightSubtreeIndex, right - 1);
return isRightValid;
}
public:
// bool verifyPostorder(vector<int>& postorder)
bool verifyPostorder(vector<int> &i_postorder)
{
return verifyPostorder(i_postorder, 0, i_postorder.size() - 1);
}
};