完全二叉树-插入节点并保持仍然是完全二叉树

完全二叉树中，层次遍历的相关问题

这里有一个问题，如果我们要对一个完全二叉树进行节点插入那么我们应该去如何解决这个问题

我们观察完全二叉树的结构与对其进行层次遍历可以发现，如果我们层次遍历时碰到的第一个节点无左孩子节点那么就应该在该节点进行插入节点操作，将插入节点作为器左孩子，如果遇到一个节点有左孩子但无右孩子，那么我们的操作其实就是在该节点将插入节点作为其右孩子。所以层次遍历可以很好的解决完全二叉树的插入问题，时间复杂度为o（n）。

那么我这里给出代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

typedef struct {
    struct TreeNode* root;
    struct TreeNode* queue[100000];
    int front;
    int rear;    
} CBTInserter;


CBTInserter* cBTInserterCreate(struct TreeNode* root) {
    CBTInserter* ans = (CBTInserter*)malloc(sizeof(CBTInserter));
    ans->root = root;
    ans->front = 0;
    ans->rear = 0;
    struct TreeNode *curr = NULL;
    ans->queue[ans->rear++] = root;
    while (ans->front != ans->rear) {
        curr = ans->queue[ans->front];
        if (curr->left) {
            ans->queue[ans->rear++] = curr->left;
        } else {
            return ans;
        }
        if (curr->right) {
            ans->queue[ans->rear++] = curr->right;
        } else {
            return ans;
        }
        ans->front++;
    }.
    return ans;
}

int cBTInserterInsert(CBTInserter* obj, int v) {
    struct TreeNode *newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = v;
    newNode->left = NULL;
    newNode->right = NULL;
    int ans = (obj->queue[obj->front])->val;
    if (obj->queue[obj->front]->left == NULL) {
        obj->queue[obj->front]->left = newNode;
    } else {
        obj->queue[obj->front++]->right = newNode;
    }
    obj->queue[obj->rear++] = newNode;
    return ans;
}

struct TreeNode* cBTInserterGet_root(CBTInserter* obj) {
    return obj->root;
}

void cBTInserterFree(CBTInserter* obj) {
    free(obj);
}

/**
 * Your CBTInserter struct will be instantiated and called as such:
 * CBTInserter* obj = cBTInserterCreate(root);
 * int param_1 = cBTInserterInsert(obj, v);
 
 * struct TreeNode* param_2 = cBTInserterGet_root(obj);
 
 * cBTInserterFree(obj);
*/

该算法思想是我们先初始一个存储树指针的数组，然后通过层次遍历将完全二叉树每个节点存储在该数组中，之后当我们找到那个插入节点的时候，我们停下遍历，返回队列的最后一个数据，也就是我们将要进行插入的指针。

同样，如果我们想要直接完全遍历二叉树，我们可以直接取消判断条件
代码修改如下：

CBTInserter* cBTInserterCreate(struct TreeNode* root) {
    CBTInserter* ans = (CBTInserter*)malloc(sizeof(CBTInserter));
    ans->root = root;
    ans->front = 0;
    ans->rear = 0;
    struct TreeNode *curr = NULL;
    ans->queue[ans->rear++] = root;
    while (ans->front != ans->rear) {
        curr = ans->queue[ans->front];
        if (curr->left) {
            ans->queue[ans->rear++] = curr->left;
        } 
        
        if (curr->right) {
            ans->queue[ans->rear++] = curr->right;
            }
       
        ans->front++;
    }.
    return ans;
}

通过上面这个代码，我们就可以层次遍历树，且非递归，也是可以学习的，层次遍历书的精髓在于，我们初始时要让队列里有数据，然后每次取出一个数据，对其进行左右子节点进行检查，存在就加入队列，之后反复上述操作，直到队列里没有数据为止。