Programming/919CompleteBinaryTreeInserter.java at master · rajucomp/Programming · GitHub

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//https://leetcode.com/problems/complete-binary-tree-inserter/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class CBTInserter {

    List<TreeNode> tree;

    public CBTInserter(TreeNode root) {
        tree = new ArrayList();
        bfs(root);
    }

    public int insert(int val) {
        tree.add(new TreeNode(val));
        TreeNode parent = null;
        if(tree.size() % 2 == 0) {
            parent = tree.get((tree.size() - 1) / 2);
            parent.left = tree.get(tree.size() - 1);
        }
        else {
            parent = tree.get((tree.size() - 2) / 2);
            parent.right = tree.get(tree.size() - 1);
        }
        return parent.val;
    }

    public TreeNode get_root() {
        return tree.get(0);
    }

    void bfs(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            tree.add(node);
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
    }
}

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

    public CBTInserter(TreeNode root) {
        nodeQueue = new LinkedList();
        bfs(root);
    }

    public int insert(int val) {
        return insert(new TreeNode(val));
    }

    int insert(TreeNode val) {
        TreeNode node = nodeQueue.peek();
        if(node.left == null) {
            node.left = val;
        }
        else {
            node.right = val;
            nodeQueue.poll();
            nodeQueue.offer(node.left);
            nodeQueue.offer(node.right);
        }
        return node.val;
    }

    public TreeNode get_root() {
        return this.root;
    }

    void bfs(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        TreeNode newRoot = new TreeNode(root.val);
        this.root = newRoot;
        nodeQueue.add(newRoot);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node.left != null) {
                queue.offer(node.left);
                insert(new TreeNode(node.left.val));
            }
            if(node.right != null) {
                queue.offer(node.right);
                insert(new TreeNode(node.right.val));
            }
        }
    }
}

/**
 * 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();
 */

/**
 * 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();
 */