1.题目要求:
完全二叉树 是每一层(除最后一层外)都是完全填充(即,节点数达到最大)的,并且所有的节点都尽可能地集中在左侧。设计一种算法,将一个新节点插入到一棵完全二叉树中,并在插入后保持其完整。实现 CBTInserter 类:CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构;
CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val的新节点 TreeNode。使树保持完全二叉树的状态,并返回插入节点 TreeNode 的父节点的值;
CBTInserter.get_root() 将返回树的头节点。
2.题目示例:
3.题目代码:
/*** 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_t;//设置队列用于层序遍历queue<TreeNode*> quence;CBTInserter(TreeNode* root) {root_t = root;//把初始后的树根放入队列中 quence.push(root);}int insert(int val) {//设置父亲结点的值int parent_value;while(quence.size() != 0){TreeNode* temp = quence.front();//如果队列的头节点两边都不为空,则进行正常的层序遍历if(temp->left != NULL&&temp->right != NULL){quence.push(temp->left);quence.push(temp->right);quence.pop();}else{//如果不是,则判断是那个树的左右子树那个是空的,再进行结点挂接if(temp->left == NULL){temp->left = new TreeNode(val);parent_value = temp->val;break;}if(temp->right == NULL){temp->right = new TreeNode(val);parent_value = temp->val;break;}}}return parent_value;}TreeNode* get_root() {//返回根节return root_t;}
};/*** Your CBTInserter object will be instantiated and called as such:* CBTInserter* obj = new CBTInserter(root);* int param_1 = obj->insert(val);* TreeNode* param_2 = obj->get_root();*/