919. Complete Binary Tree Inserter - Medium

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

导读：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]]

Note:

The initial given tree is complete and contains between?1?and?1000?nodes.
CBTInserter.insert?is called at most?10000?times per test case.
Every value of a given or inserted node is between?0?and?5000.

M1:?

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

以bfs的顺序，用List存tree nodes：tree[i]的左孩子tree[2i+1]、右孩子tree[2i+2]

当insert第n个node时，可以通过index找到它的parent: tree[(n-1)/2]

initialization: time = O(n),space = O(n)

insert: time = O(1),space = O(1)

get_root: time = O(1),space = O(1)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class CBTInserter {
    
    List<TreeNode> tree;
    TreeNode root;

    public CBTInserter(TreeNode root) {
        tree = new ArrayList<>();
        this.root = root;
        tree.add(root);
        for(int i = 0; i < tree.size(); i++) {
            if(tree.get(i).left != null) {
                tree.add(tree.get(i).left);
            }
            if(tree.get(i).right != null) {
                tree.add(tree.get(i).right);
            }
        }
    }
    
    public int insert(int v) {
        int size = tree.size();
        TreeNode node = new TreeNode(v);
        tree.add(node);
        if(size % 2 == 0) {
            tree.get((size - 1) / 2).right = node;
        } else {
            tree.get((size - 1) / 2).left = node;
        }
        return tree.get((size - 1) / 2).val;
    }
    
    public TreeNode get_root() {
        return tree.get(0);
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(v);
 * TreeNode param_2 = obj.get_root();
 */

M2: 用queue存

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

Traverse the binary tree by level order;
If the current node has left and right child,pop it out,and add both of its children into the queue; otherwise,insert new node as its child;
repeat the above till encounter the first node that does NOT have two children.

initialization: time = O(n),space = O(1)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class CBTInserter {
    
    Queue<TreeNode> q;
    TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root = root;
        q = new LinkedList<>();
        q.offer(root);
        while(q.peek().left != null && q.peek().right != null) {
            q.offer(q.peek().left);
            q.offer(q.peek().right);
            q.poll();
        }
    }
    
    public int insert(int v) {
        TreeNode node = q.peek();
        if(node.left == null) {
            node.left = new TreeNode(v);
        } else {
            node.right = new TreeNode(v);
            q.offer(node.left);
            q.offer(node.right);
            q.poll();
        }
        return node.val;
    }
    
    public TreeNode get_root() {
        return root;
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(v);
 * TreeNode param_2 = obj.get_root();
 */

（编辑：李大同）

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