题目
完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。
实现 CBTInserter 类:
CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val的新节点 TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
CBTInserter.get_root() 将返回树的头节点。
示例 1：
输入 ["CBTInserter", "insert", "insert", "get_root"] [[[1, 2]], [3], [4], []] 输出 [null, 1, 2, [1, 2, 3, 4]] 解释 CBTInserter cBTInserter = new CBTInserter([1, 2]); cBTInserter.insert(3); // 返回 1 cBTInserter.insert(4); // 返回 2 cBTInserter.get_root(); // 返回 [1, 2, 3, 4]
解题
方法一：双队列—O(1)复杂度插入
如果每次插入的时候都进行层序遍历，那么如果在插入情况比较多的时候，效率会很低。
如果能直接从队列中取出节点，然后插入，那么就会快很多。
由于是完美二叉树，被插入的节点，只可能是2种状态
- 没有左、右子节点， 这种情况下后续是先插入左节点
- 有左子节点，没右子节点，这种情况下，插入右节点
初始化的时候将情况1，存储在q_L队列中，将情况2，存储在q_R队列中。
因此可以通过层序遍历，初始化q_L,q_R队列
由于完全二叉树的特性，插入的时候，优先从q_R队列中取值。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class CBTInserter { public: TreeNode* root; queue<TreeNode*> q_L;//存放没有左右孩子的节点 queue<TreeNode*> q_R;//存放没有右孩子的节点 CBTInserter(TreeNode* root) {//目的是为了初始化q_L和q_R队列 this->root=root; queue<TreeNode*> q; q.push(root); while(!q.empty()){ TreeNode* cur=q.front(); q.pop(); if(!cur->left&&!cur->right) q_L.push(cur); if(cur->left&&!cur->right) q_R.push(cur); if(cur->left) q.push(cur->left); if(cur->right) q.push(cur->right); } } int insert(int val) { if(!q_R.empty()){//优先取仅没有右孩子的节点(因为完全二叉树的特点) TreeNode* cur=q_R.front(); q_R.pop(); cur->right=new TreeNode(val); q_L.push(cur->right); return cur->val; } else{//取没有左右孩子的节点 TreeNode* cur=q_L.front(); q_L.pop(); cur->left=new TreeNode(val); q_R.push(cur); q_L.push(cur->left); return cur->val; } } TreeNode* get_root() { return root; } };
方法二：插入时–层序遍历
class CBTInserter { public: TreeNode* root; CBTInserter(TreeNode* root) { this->root=root; } int insert(int val) { queue<TreeNode*> q; q.push(root); while(!q.empty()){ TreeNode* cur=q.front(); q.pop(); if(cur->left) q.push(cur->left); else{ cur->left=new TreeNode(val); return cur->val; } if(cur->right) q.push(cur->right); else{ cur->right=new TreeNode(val); return cur->val; } } return -1; } TreeNode* get_root() { return root; } };
方法三：单队列—O(1)复杂度插入
其实和方法一几乎是一样的，但是方法一可以改进。
因为是完全二叉树的特点，因为必定可能保证，优先把只有左叶子节点的节点的取出来，然后才会取没有左右节点的叶子节点。
class CBTInserter { public: queue<TreeNode*> q; TreeNode* root; CBTInserter(TreeNode* root) { this->root=root; queue<TreeNode*> q_tmp; q_tmp.push(root); while(!q_tmp.empty()){ TreeNode* cur=q_tmp.front(); q_tmp.pop(); if(!cur->left||!cur->right) q.push(cur); if(cur->left) q_tmp.push(cur->left); if(cur->right) q_tmp.push(cur->right); } } int insert(int val) { TreeNode* cur=q.front(); if(cur->left){ cur->right=new TreeNode(val); q.pop(); q.push(cur->right); } else{ cur->left=new TreeNode(val); q.push(cur->left); } return cur->val; } TreeNode* get_root() { return root; } };
