江门网站制作维护,重庆网站制作公司重庆,投资管理公司,装备2合1合成版传奇手游1. 题目
完全二叉树是每一层#xff08;除最后一层外#xff09;都是完全填充#xff08;即#xff0c;结点数达到最大#xff09;的#xff0c;并且所有的结点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter#xff0c;它支持以下几种操作…1. 题目
完全二叉树是每一层除最后一层外都是完全填充即结点数达到最大的并且所有的结点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter它支持以下几种操作
CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val v 的树中以使其保持完全二叉树的状态并返回插入的 TreeNode 的父结点的值CBTInserter.get_root() 将返回树的头结点。
示例 1
输入inputs [CBTInserter,insert,get_root],
inputs [[[1]],[2],[]]
输出[null,1,[1,2]]示例 2
输入inputs [CBTInserter,insert,insert,get_root],
inputs [[[1,2,3,4,5,6]],[7],[8],[]]
输出[null,3,4,[1,2,3,4,5,6,7,8]]提示
最初给定的树是完全二叉树且包含 1 到 1000 个结点。
每个测试用例最多调用 CBTInserter.insert 操作 10000 次。
给定结点或插入结点的每个值都在 0 到 5000 之间。来源力扣LeetCode 链接https://leetcode-cn.com/problems/complete-binary-tree-inserter 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
先按层序将树的节点放进数组并将节点之间的连接关系拆开用一个队列存储完全二叉树中的节点其子节点没插满的节点
class CBTInserter {TreeNode *r NULL;vectorTreeNode* insertNode;//存储原始树的各个节点int i, fatherVal;queueTreeNode* upperLv;//存储完全二叉树子节点没插满的节点TreeNode *tp;
public:CBTInserter(TreeNode* root) {lvOrder(root);//树节点层序添加进数组并拆散待用if(r NULL){r insertNode.front();insertNode.erase(insertNode.begin());upperLv.push(r);}while(!insertNode.empty()){tp insertNode.front();insertNode.erase(insertNode.begin());upperLv.push(tp);//tp的子节点没有满if(upperLv.front()-left NULL)upperLv.front()-left tp;else//左边接上了接在右边{upperLv.front()-right tp;upperLv.pop();//左右都接好了上层的可以删了}}}int insert(int v) {fatherVal upperLv.front()-val;tp new TreeNode(v);if(upperLv.front()-left NULL)upperLv.front()-left tp;else//左边接上了接在右边{upperLv.front()-right tp;upperLv.pop();//左右都接好了上层的可以删了}upperLv.push(tp);//tp的子节点没有满return fatherVal;}TreeNode* get_root() {return r;}void lvOrder(TreeNode *root){if(root NULL)return;insertNode.clear();insertNode.push_back(root);for(i 0; i insertNode.size(); i){if(insertNode[i]-left)insertNode.push_back(insertNode[i]-left);if(insertNode[i]-right)insertNode.push_back(insertNode[i]-right);insertNode[i]-left insertNode[i]-right NULL;//拆散整棵树后面直接利用节省内存}}
};
