美文网首页
24 二叉搜索树的后序遍历序列

24 二叉搜索树的后序遍历序列

作者: Juge100 | 来源:发表于2018-10-12 16:30 被阅读0次

    二叉搜索树的后续遍历

    题目描述:

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

    解题思路:

    1. 根据后续遍历的特点,每次遍历到根结点的时候都是最后一位
    2. 而二叉搜索树的特点就是左子树都小于等于root,右子树都大于等于root
    3. 所以,先找到根结点,然后由前向后遍历该序列
    4. 开始的部分的数值应该都是小于等于root的(左子树),当某个结点大于root的值的时候,此结点开始就是右子树
    5. 遍历右子树的所有数值(后序遍历的中后段),如果有数值小于root,则说明该序列不是后续遍历序列
    6. 递归地判断做子树和右子树,如果左右子树也都是满足后续遍历的特点,那么整个序列就都满足后续遍历的特点。

    代码:

    class Solution {
    public:
        bool VerifySquenceOfBST(vector<int> sequence) {
            if (sequence.empty()) {
                return false;
            }
            int length = sequence.size();
            int root = sequence[length - 1];
    
            // 从前向后遍历sequence序列
            int i = 0;
            for (; i < length - 1; ++i) {
                if (sequence[i] > root) 
                    break;
            }
    
            // 用另外一个变量来记录右子树开始的地方
            int j = i;
            // 遍历右子树,如果右子树中有元素小于root,则返回false
            for (; j < length - 1; j++) {
                if (sequence[j] < root) {
                    return false;
                }
            }
    
            bool left = true;
            bool right = true;
            vector<int> leftSeq, rightSeq;
            for (int count = 0; count < i; ++count) {
                leftSeq.push_back(sequence[count]);
            }
            for (int count = i; count < length - 1; ++count) {
                rightSeq.push_back(sequence[count]);
            }
    
            // 如果左子树不是空树,即左子树的结尾结点大于0
            // 递归验证左半子树
            if (i > 0) {
                left = VerifySquenceOfBST(leftSeq);
            }
            // 如果右子树不是空树
            // 递归验证右半子树
            if (i < length - 1) {
                right = VerifySquenceOfBST(rightSeq);
            }
    
            return left && right;
        }
    };
    

    2018.10.12

    相关文章

      网友评论

          本文标题:24 二叉搜索树的后序遍历序列

          本文链接:https://www.haomeiwen.com/subject/xeygaftx.html