leetcode-919：完全二叉树插入器 题目解题方法一：双队列---O(1)复杂度插入方法二：插入时--层序遍历 题目
题目连接
完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。
实现 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; } };
 1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。 |