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","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]]
1 class CBTInserter { 2 private TreeNode root; 3 4 public CBTInserter(TreeNode root) { 5 this.root = root; 6 } 7 8 public int insert(int v) { 9 Queue<TreeNode> q = new LinkedList<>(); 10 q.offer(root); 11 while (!q.isEmpty()) { 12 TreeNode n = q.poll(); 13 if (n.right != null) { // n has 2 children. 14 q.offer(n.left); 15 q.offer(n.right); 16 } else { 17 if (n.left == null) { 18 n.left = new TreeNode(v); 19 } else { 20 n.right = new TreeNode(v); 21 } 22 return n.val; 23 } 24 } 25 return -1; 26 } 27 28 public TreeNode get_root() { 29 return root; 30 } 31 }
还有一种方法是把没有两个children的node单独放在一个queue里面，这样每次添加的时候，从queue的head取就知道那个是parent.
1 class CBTInserter { 2 private TreeNode root; 3 private Queue<TreeNode> nodesWithNullChild; 4 5 public CBTInserter(TreeNode root) { 6 this.root = root; 7 this.nodesWithNullChild = new LinkedList<>(); 8 Queue<TreeNode> q = new LinkedList<>(); 9 q.offer(root); 10 while (!q.isEmpty()) { 11 TreeNode n = q.poll(); 12 if (n.left == null || n.right == null) { 13 nodesWithNullChild.offer(n); 14 } 15 if (n.left != null) { 16 q.offer(n.left); 17 } 18 if (n.right != null) { 19 q.offer(n.right); 20 } 21 } 22 } 23 24 public int insert(int v) { 25 TreeNode newNode = new TreeNode(v); 26 TreeNode firstNode = nodesWithNullChild.peek(); 27 if (firstNode.left == null) { 28 firstNode.left = newNode; 29 } else { 30 firstNode.right = newNode; 31 nodesWithNullChild.poll(); 32 } 33 nodesWithNullChild.offer(newNode); 34 return firstNode.val; 35 } 36 37 public TreeNode get_root() { 38 return root; 39 } 40 }
919. Complete Binary Tree Inserter
原文：https://www.cnblogs.com/beiyeqingteng/p/14527401.html