leetcode_919.CompleteBinaryTreeInserter

https://leetcode.com/problems/complete-binary-tree-inserter/

设计一个CBTInserter，使用给定完全二叉树初始化。三个功能;

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

主要涉及完全二叉树的插入。

解法一：dfs based

对给定的完全二叉树，先计算其最大高度maxlayer，以及深度最深的节点数numoflastlayer。如果numoflastlayer<2^(maxlayer-1)，说明应该在maxlayer-1层第一个子节点数小于2的节点插入；如果numoflastlayer==2^(maxlayer-1)，说明应该在maxlayer层第一个子节点处插入，利用dfs可以完成。插入过后及时更新maxlager和numoflastlayer。

class CBTInserter{public: void preorder(TreeNode* root,int layer){ if(layer>maxlayer){ maxlayer = layer; numoflastlayer = 1; }else if(layer == maxlayer) numoflastlayer++; if(root->left!=NULL) preorder(root->left, layer+1); if(root->right!=NULL) preorder(root->right, layer+1); } CBTInserter(TreeNode* root){ root_ =root; maxlayer=-1; numoflastlayer=0; preorder(root,0); } TreeNode* Insert(TreeNode* root, int v, int layer, int insertlayer){ if(layer == insertlayer-1){ if(root->left == NULL){ root->left = new TreeNode(v); return root; }else if(root->right == NULL){ root->right = new TreeNode(v); return root; } }else{ TreeNode* res = Insert(root->left, v, layer+1, insertlayer); if(res == NULL) res = Insert(root->right, v, layer+1, insertlayer); return res; } return NULL; } int insert(int v){int maxnumoflastlayer = pow(2, maxlayer); TreeNode* res = NULL; if(numoflastlayerval; } TreeNode* get_root(){ return root_; }private: TreeNode* root_; int maxlayer; int numoflastlayer;};

解法二：bfs based

先使用bfs将所有子节点数为0和1的节点存入队列，然后维护这个队列，对头节点是插入新节点的节点，若对头节点只有右子树为NULL，那么插入后将其pop，并将其两个子节点指针压入队列。

class CBTInserter{public: TreeNode* root_; queue nodes_0_1; CBTInserter(TreeNode* root){ root_ = root; queue que; que.push(root); while(!que.empty()){ TreeNode* now = que.front(); que.pop(); if(now->left == NULL) nodes_0_1.push(now); else if(now->right == NULL) nodes_0_1.push(now); else{ que.push(now->left); que.push(now->right); } } } int insert(int v){ TreeNode* root = nodes_0_1.front(); if(root->left!=NULL){ root->right = new TreeNode(v); nodes_0_1.pop(); nodes_0_1.push(root->left); nodes_0_1.push(root->right); } else root->left = new TreeNode(v); return root->val; } TreeNode* get_root(){ return root_; }};