919.complete binary tree inserter

发布时间：2020-12-14 04:17:34 所属栏目：大数据来源：网络整理

导读：A? complete ?binary tree is a binary tree in which every level,except possibly the last,is completely filled,and all nodes are as far left as possible. Write a data structure? CBTInserter ?that is initialized with a complete binary tree an

A?complete?binary tree is a binary tree in which every level,except possibly the last,is completely filled,and all nodes are as far left as possible.

Write a data structure?CBTInserter?that is initialized with a complete binary tree and supports the following operations:

CBTInserter(TreeNode root)?initializes the data structure on a given tree?with head node?root;
CBTInserter.insert(int v)?will insert a?TreeNode?into the tree with value?node.val =?v?so that the tree remains complete,?and returns the value of the parent of the inserted?TreeNode;
CBTInserter.get_root()?will return the head node of the tree.

Example 1:

Input: inputs = ["CBTInserter","insert","get_root"],inputs = [[[1]],[2],[]] Output: [null,1,[1,2]]

Example 2:

Input: inputs = ["CBTInserter",inputs = [[[1,2,3,4,5,6]],[7],[8],[]] Output: [null,6,7,8]]

树的广度优先搜索(利用队列实现）+ 完全二叉树父节点和子节点的下标索引关系

class CBTInserter {
    TreeNode *root{nullptr};
    vector<TreeNode *> nodes;
    void bfs(TreeNode* root){
        queue<TreeNode*> qu;
        if(root) qu.push(root);
        while(!qu.empty()){
            TreeNode* parent=qu.front();
            nodes.push_back(parent);
            qu.pop();
            if(parent->left)
                qu.push(parent->left);
            if(parent->right)
                qu.push(parent->right);
        }
    }

public:
    CBTInserter(TreeNode *root) {
        this->root = root;
        bfs(root);
    }

    int insert(int v) {
        TreeNode *node = new TreeNode(v);
        nodes.push_back(node);
        int sz=nodes.size();
        TreeNode* parent=nodes[sz/2-1];
        cout<<"parent idx: "<<sz/2-1<<endl;
        if(sz%2==0)
            parent->left=node;
        else
            parent->right=node;
//        if(sz==1) return 0;   测试用例没有考虑构造函数调用为 CBTInserter(nullptr) 的情况
        return parent->val;
    }

    TreeNode *get_root() {
        return root;
    }
};

去掉queue

class CBTInserter {
    TreeNode *root{nullptr};
    vector<TreeNode *> nodes;
    void bfs(TreeNode* root){
        if(root==nullptr) return;
        nodes.push_back(root);
        int i=0;//i表示当前父节点的索引
        int sz=1;//s表示当前向量nodes的长度
        while(i<sz){
            TreeNode* parent=nodes[i];
            if(parent->left){
                nodes.push_back(parent->left);
                sz+=1;
            }
            if(parent->right){
                nodes.push_back(parent->right);
                sz+=1;
            }
            i++;
        }
    }

public:
    CBTInserter(TreeNode *root) {
        this->root = root;
        bfs(root);
    }

    int insert(int v) {
        TreeNode *node = new TreeNode(v);
        nodes.push_back(node);
        int sz=nodes.size();
        TreeNode* parent=nodes[sz/2-1];
        cout<<"parent idx: "<<sz/2-1<<endl;
        if(sz%2==0)
            parent->left=node;
        else
            parent->right=node;
//        if(sz==1) return 0;   测试用例没有考虑构造函数调用为 CBTInserter(nullptr) 的情况
        return parent->val;
    }

    TreeNode *get_root() {
        return root;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!