AcWing 46. 二叉搜索树的后序遍历序列（中序和后序遍历）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 46. 二叉搜索树的后序遍历序列（中序和后序遍历）原题链接简单

作者：

天命 , 2020-05-09 15:58:32 , 所有人可见 , 阅读 2609

10

5


class Solution {

public:

    bool verifySequenceOfBST(vector<int> sequence) { //方法一，利用中序和后序来重建二叉树
        vector<int> in;
        in = sequence;
        int n = in.size();
        sort(in.begin(), in.end());
        return build(sequence, in, 0, n - 1, 0, n - 1);
    }

    bool build(vector<int> &post, vector<int> &in, int il, int ir, int pl, int pr){
        if(pl > pr) return true;
        int root = post[pr];
        int k;
        for(k = il; k <= ir; k++){
            if(in[k] == root) break;
        }
        int num = k - il;

        for(int i = pl; i <= pl + num - 1; i++){    //后序遍历当前左子树内有大于根节点的值
            if(post[i] > root) return false;
        }
        return(k > pl ? build(post, in, il, k - 1, pl, pl + num - 1):true) && 
        (k < pr ? build(post, in, k + 1, ir, pl + num, pr - 1):true);
    }
};

9 评论

Zh_Ivan 2021-10-13 09:16

class Solution {
public:
    vector<int> inOrder, postOrder;
    unordered_map<int, int> pos;
    bool verifySequenceOfBST(vector<int> sequence) {
        postOrder = sequence;
        sort(sequence.begin(), sequence.end());
        inOrder = sequence;
        for(int i = 0; i < inOrder.size(); i++)
            pos[inOrder[i]] = i;
        return build(0, sequence.size() - 1, 0, sequence.size() - 1);
    }

    bool build(int inL, int inR, int postL, int postR){
        if(postL > postR)   return true;
        int root = postOrder[postR];
        int k = pos[root];

        if(k < inL || k > inR)  return false;
        return build(inL, k - 1, postL, postL + k - 1 - inL) && build(k + 1, inR, postL + k - inL, postR - 1);
    }
};