LeetCode 919. Complete Binary Tree Inserter

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

导读：原题链接在这里：https://leetcode.com/problems/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. Wri

原题链接在这里：https://leetcode.com/problems/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:

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.

题解：

Do level order traversal on the tree. Keep the nodes that doesn‘t have both left and right child in the queue.

Pop the first node in the queue and mark it as current.

When inserting,check current node‘s left,if null,insert it as left child. Or check current node‘s right,insert it as right child. If both not null,then pop another node from queue and insert it as left child.

Time Complexity:?CBTInserter,O(n).?insert,O(1).?get_root,O(1).

Space: O(n). queue space.

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class CBTInserter {
11     TreeNode root;
12     TreeNode cur;
13     LinkedList<TreeNode> que;
14     public CBTInserter(TreeNode root) {
15         this.root = root;
16         que = new LinkedList<TreeNode>();
17         que.add(root);
18         while(que.peek().left != null && que.peek().right != null){
19             TreeNode top = que.poll();
20             que.add(top.left);
21             que.add(top.right);
22         }
23         
24         cur = que.poll();
25         if(cur.left != null){
26             que.add(cur.left);
27         }
28     }
29     
30     public int insert(int v) {
31         TreeNode newNode = new TreeNode(v);
32         que.add(newNode);
33         
34         if(cur.left == null){
35             cur.left = newNode;
36         }else if(cur.right == null){
37             cur.right = newNode;
38         }else{
39             cur = que.poll();
40             cur.left = newNode;
41         }
42         
43         return cur.val;
44     }
45     
46     public TreeNode get_root() {
47         return this.root;
48     }
49 }
50 
51 /**
52  * Your CBTInserter object will be instantiated and called as such:
53  * CBTInserter obj = new CBTInserter(root);
54  * int param_1 = obj.insert(v);
55  * TreeNode param_2 = obj.get_root();
56  */

类似Check Completeness of a Binary Tree.

（编辑：李大同）

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