919. Complete Binary Tree Inserter

曾经终败给现在 2024-04-08 09:28 65阅读 0赞

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.

Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion.

Implement the `CBTInserter` class:

*  `CBTInserter(TreeNode root)` Initializes the data structure with the `root` of the complete binary tree.
 *  `int insert(int v)` Inserts a `TreeNode` into the tree with value `Node.val == val` so that the tree remains complete, and returns the value of the parent of the inserted `TreeNode`.
 *  `TreeNode get_root()` Returns the root node of the tree.

**Example 1:**

![b6f60d33be7714c5c44d7f93eef498db.jpeg][]

Input
    ["CBTInserter", "insert", "insert", "get_root"]
    [[[1, 2]], [3], [4], []]
    Output
    [null, 1, 2, [1, 2, 3, 4]]
    
    Explanation
    CBTInserter cBTInserter = new CBTInserter([1, 2]);
    cBTInserter.insert(3);  // return 1
    cBTInserter.insert(4);  // return 2
    cBTInserter.get_root(); // return [1, 2, 3, 4]

**Constraints:**

*  The number of nodes in the tree will be in the range `[1, 1000]`.
 *  `0 <= Node.val <= 5000`
 *  `root` is a complete binary tree.
 *  `0 <= val <= 5000`
 *  At most `104` calls will be made to `insert` and `get_root`.

题目：实现一个类，可以往二叉树中插入节点，使得二叉树保持完全二叉树

思路：容易错的点是初始化时不只是一个根节点，可能已经是一棵树。用queue来保存所有不完全的子节点。代码

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class CBTInserter {
    private:
        queue<TreeNode*> q;
        TreeNode* rootNode;
    public:
        CBTInserter(TreeNode* root) {
            rootNode = root;
            q.push(root);
            while(!q.empty()){
                if(q.front()->left) q.push(q.front()->left);
                if(q.front()->right) q.push(q.front()->right);
                if(q.front()->left && q.front()->right)
                    q.pop();
                else break;
            }
        }
        
        int insert(int val) {
            TreeNode* node = new TreeNode(val);
            int res = q.front()->val;
            if(!q.front()->left){
                q.front()->left = node;
            } else {
                q.front()->right = node;
                q.pop();
            }
            q.push(node);
            return res;
        }
        
        TreeNode* get_root() {
            return rootNode;
        }
    };
    
    /**
     * Your CBTInserter object will be instantiated and called as such:
     * CBTInserter* obj = new CBTInserter(root);
     * int param_1 = obj->insert(val);
     * TreeNode* param_2 = obj->get_root();
     */

[b6f60d33be7714c5c44d7f93eef498db.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/95668a6aa96a46bea47bccd3bbd6c6d2.jpeg