【剑指Offer】T33 判断是否是二叉搜索树的后序序列

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

思路:

  • 例如 5、7、6、9、11、10、8
    • 二叉树后序序列,最后一个数字为根节点值
    • 前三个小于 8,后三个大于 8,分别为左子树和右子树。子序列内也满足,6 为根,5 小于,7 大于。
  • 再如 7、4、6、5
    • 5 为根节点
    • 7 大于 5,可能没有左子树
    • 但是右子树上却右 4 小于 5,不满足右子树大于根节点,不符合
  • 故找到根节点,再往后遍历
    • 都小于根的序列定义为左子树序列
    • 再判断右边序列是否都大于根节点
    • 递归
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int len = sequence.size();
        if(len == 0)
           return false;
        if(len == 1)
            return true;
        int gen = sequence[len-1]; // 根节点值
        
        vector<int> left;
        vector<int> right;
        int i; // 左子树序列,都小于根节点
        for(i = 0; i < len, sequence[i] < gen; i++){
            // 入左子树序列
            left.push_back(sequence[i]);
        }
        
        if(i < len-1){// 还有右子树序列时
            for(int j = i+1; j < len-i; j++){
                // 右子树序列有小与根节点的值
                if(sequence[j] < gen)
                    return false;
                // 同时入右子树序列
                right.push_back(sequence[j]);
            }
        }
        return VerifySquenceOfBST(left) && VerifySquenceOfBST(right);
    }
};

上述没通过所有测试用例,边界值情况,也就是递归出口十分混乱。

当子序列至少右两个的时候才进入下一轮递归。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int len = sequence.size();
        if(len <= 0)
           return false;
        
        int gen = sequence[len-1]; // 根节点值
        
        vector<int> left;
        vector<int> right;
        
        int i; // 左子树序列下标,都小于根节点
        for(i = 0; i < len-1, sequence[i] < gen; i++){// len-1是因为末尾是根节点
            // 入左子树序列
            left.push_back(sequence[i]);
        }
        
        if(i < len-1){// 还有右子树序列时
            for(int j = i; j < len-1; j++){
                // 右子树序列有小与根节点的值
                if(sequence[j] < gen)
                    return false;
                // 同时入右子树序列
                right.push_back(sequence[j]);
            }
        }
        
        bool bleft = true, bright = true;
        // 根节点大于1时才进入下一轮递归,因为通过上面两轮循环,子序列肯定满足条件
        if(left.size() > 1)
            bleft = VerifySquenceOfBST(left);
        if(right.size() > 1)
            bright = VerifySquenceOfBST(right);
        return bleft && bright;
    }
};

本文链接:https://ariser.cn/index.php/archives/382/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!