二叉树的后序遍历序列

---

---

题目描述

输入一个整数数组，判断该数组是否为某二叉树搜索树的后序遍历的结果。如果是输出Yes，否则输出No。假设输入的数组的任意两个数字都是互不相同的。

解题思路

二叉树分左右子树，不可交换。通过大小来区分左右子树。左子树的根节点小于根节点；右子树的根节点大于根节点。

后序遍历：从叶子结点开始，从左子树到右子树依次遍历，最后遍历根结点。

根据后序遍历的原理可知，后序遍历输出序列，除最后一个元素为根结点外，分为两段，前半段为小于根节点的左子树，后半段为大于根结点的右子树。

然后可以根据后续遍历输出序列的特点，来判断输入的数组是否为该树的后序遍历。

主要是先保证数组元素小于根结点的左子树先正确，然后判断剩余的元素是否满足右子树的要求（大于根结点）

代码

class Solution
{
public:
    bool VerifySquenceOfBST(vector<int> sequence)
    {
        return sub(sequence, 0, sequence.size()-1);
    }
private:
    bool sub(vector<int> seq, int begin, int end)
    {
        if (seq.size()==0 || begin>end)
            return false;
        
        int i = begin; // i就是左右子树的分界值
        // 分出左树
        for (;i < end; i++)
        {
            if (seq[i] > seq[end]) // 大于根结点则跳出该循环
                break;
        }
        
        // 查看右树是否满足后续遍历要求
        for (int j = i; j<end; j++)
        {
            if (seq[j] < seq[end])
                return false;
        }
        
        // 判断左子树是否满足后序遍历要求
        bool left = true;
        if (i > begin)
        {
            left = sub(seq, begin, i-1);
        }
        
        // 判断右子树是否满足后序遍历要求
        bool right = true;
        if (i < end)
        {
            right = sub(seq, i, end-1);
        }
        
        return left&&right; // 只有左右子树都满足后续遍历要求才为真
    }
};

---

参考博文链接：https://cuijiahua.com/blog/2017/12/basis_23.html