leetcode-919-Complete-Binary-Tree-Inserter

发表于   |  

描述

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:

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

Example 2:

1
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.

分析

题目给定了一个二叉树，要求写一个二叉树操作类，这个类可以初始化一个二叉树，插入二叉树，获取二叉树的根节点。可以使用数组来存储，就跟堆使用数组来表示二叉树一样，如果父节点的索引是 i，左子树则为 $2i$，右子树为 $2i+1$，初始化的时间复杂度是 $O(n)$，插入，获取根节点的复杂度是 $O(1)$。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 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;
    public CBTInserter(TreeNode root) {
        tree = new ArrayList<>();
        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 treeSize = tree.size();
        TreeNode node = new TreeNode(v);
        tree.add(node);
        if (treeSize % 2 == 1) {
            tree.get((treeSize-1)/2).left = node;
        } else {
            tree.get((treeSize-1)/2).right = node;
        }
        return tree.get((treeSize-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();
 */

题目来源