919. Complete Binary Tree Inserter

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","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
Output: [null,3,4,[1,2,3,4,5,6,7,8]]

Note:

  1. The initial given tree is complete and contains between 1 and 1000 nodes.

  2. CBTInserter.insert is called at most 10000 times per test case.

  3. Every value of a given or inserted node is between 0 and 5000.

    这道题说是让实现一个完全二叉树的插入器的类,之前也做过关于完全二叉树的题 Count Complete Tree Nodes。首先需要搞清楚的是完全二叉树的定义,即对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,换句话说,完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。由于插入操作要找到最后一层的第一个空缺的位置,所以很自然的就想到了使用层序遍历的方法,由于插入函数返回的是插入位置的父结点,所以在层序遍历的时候,只要遇到某个结点的左子结点或者右子结点不存在,则跳出循环,则这个残缺的父结点刚好就在队列的首位置。那么在插入函数时,只要取出这个残缺的父结点,判断若其左子结点不存在,说明新的结点要连接在左子结点上,否则将新的结点连接在右子结点上,并把此时的左右子结点都存入队列中,并将之前的队首元素移除队列即可,参见代码如下:
    解法一:

    class CBTInserter {
    public:
    CBTInserter(TreeNode* root) {

       tree_root = root;
       q.push(root);
       while (!q.empty()) {
           auto t = q.front(); 
           if (!t->left || !t->right) break;
           q.push(t->left);
           q.push(t->right);
           q.pop();
       }
    

    }
    int insert(int v) {

       TreeNode *node = new TreeNode(v);
       auto t = q.front(); 
       if (!t->left) t->left = node;
       else {
           t->right = node;
           q.push(t->left);
           q.push(t->right);
           q.pop();
       }
       return t->val;
    

    }
    TreeNode* get_root() {

       return tree_root;
    

    }

    private:
    TreeNode *tree_root;
    queue<TreeNode*> q;
    };

    下面这种解法缩短了建树的时间,但是极大的增加了插入函数的运行时间,因为每插入一个结点,都要从头开始再遍历一次,并不是很高效,可以当作一种发散思维吧,参见代码如下:
    解法二:

    class CBTInserter {
    public:
    CBTInserter(TreeNode* root) {

       tree_root = root;
    

    }
    int insert(int v) {

       queue<TreeNode*> q{{tree_root}};
       TreeNode *node = new TreeNode(v);
       while (!q.empty()) {
           auto t = q.front(); q.pop();
           if (t->left) q.push(t->left);
           else {
               t->left = node;
               return t->val;
           }
           if (t->right) q.push(t->right);
           else {
               t->right = node;
               return t->val;
           }
       }
       return 0;
       
    

    }
    TreeNode* get_root() {

       return tree_root;
    

    }

    private:
    TreeNode *tree_root;
    };

    再来看一种不使用队列的解法,因为队列总是要遍历,比较麻烦,如果使用数组来按层序遍历的顺序保存这个完全二叉树的结点,将会变得十分的简单。而且有个最大的好处是,可以直接通过坐标定位到其父结点的位置,通过 (i-1)/2 来找到父结点,这样的话就完美的解决了插入函数要求返回父结点的要求,而且通过判断当前完整二叉树结点个数的奇偶,可以得知最后一个结点是在左子结点上还是右子结点上,这样就可以直接将新加入的结点连到到父结点的正确的子结点位置,参见代码如下:
    解法三:

    class CBTInserter {
    public:
    CBTInserter(TreeNode* root) {

       tree.push_back(root);
       for (int i = 0; i < tree.size(); ++i) {
           if (tree[i]->left) tree.push_back(tree[i]->left);
           if (tree[i]->right) tree.push_back(tree[i]->right);
       }
    

    }
    int insert(int v) {

       TreeNode *node = new TreeNode(v);
       int n = tree.size();
       tree.push_back(node);
       if (n % 2 == 1) tree[(n - 1) / 2]->left = node;
       else tree[(n - 1) / 2]->right = node;
       return tree[(n - 1) / 2]->val;
    

    }
    TreeNode* get_root() {

       return tree[0];
    

    }

    private:
    vector<TreeNode*> tree;
    };

    Github 同步地址:

https://github.com/grandyang/leetcode/issues/919

类似题目:

Count Complete Tree Nodes

参考资料:

https://leetcode.com/problems/complete-binary-tree-inserter/

https://leetcode.com/problems/complete-binary-tree-inserter/discuss/178424/C%2B%2BJavaPython-O(1)-Insert

https://leetcode.com/problems/complete-binary-tree-inserter/discuss/178528/Java-Solution%3A-O(1)-Insert-VS.-O(1)-Pre-process-Trade-Off

https://leetcode.com/problems/complete-binary-tree-inserter/discuss/178427/Java-BFS-straightforward-code-two-methods-Initialization-and-insert-time-O(1)-respectively.

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation