DAY15|| 102. 层序遍历 226. 翻转二叉树 101. 对称二叉树_inverttree(struct treenode* root)

102. 二叉树的层序遍历

思路：使用队列。根节点非空则入队，当队列不为空（front != rear）时，持续入队出队的操作，因为我们需要知道当层元素什么时候被遍历完，方便我们将结果存入二维数组，因此我们需要一个 lastRear 来存放第二个循环中最后一个入队的尾节点；当队头不等于 lastRear 时，重复操作：1. 队头元素出队，并访问它将其存入数组 ret；2. 把它的左右孩子入队（孩子不为空时）；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
struct queue {
     int front;
     int rear;
     struct TreeNode *t[2050];
};
 
struct TreeNode *Pop(struct queue *q){
     return q->t[q->front++];
 }
 
void Push(struct queue *q, struct TreeNode *x){
    q->t[q->rear++] = x;
 }
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(sizeof(int)*2050);
    int **ret = (int**)malloc(sizeof(int*)*2050);
    struct TreeNode *p = root;
    if(root == NULL)
    return NULL;
    struct queue *q = malloc(sizeof(struct queue));
    q->front = 0;
    q->rear = 0;
    if(root != NULL)Push(q, root);
    while(q->front != q->rear){
        int i = 0;
        ret[*returnSize] = (int *)malloc(sizeof(int)*(q->rear -q->front));
        int lastRear = q->rear;
        while(q->front != lastRear){
              p = Pop(q);
       ret[*returnSize][i++] = p->val;
        if(p->left != NULL)
        Push(q, p->left);
        if(p->right != NULL)
        Push(q, p->right);
        }
        (*returnColumnSizes)[*returnSize] = i;
        (*returnSize)++;
    }
    return ret;
 
}

这道题收获很多：学会标记每层树节点什么时候遍历完；明白了力扣二位数组的初始化；结构体中的变量不可以赋初值。 

 226. 翻转二叉树

思路：先序遍历，先交换根节点左右孩子，再交换左孩子和右孩子； 

收获：交换指针时，要传入指针地址，函数参数要用指向指针的指针！ 

void Swap(struct TreeNode **l, struct TreeNode **r){
    struct TreeNode *t = *l;
    *l = *r;
     *r = t;
 }
 
struct TreeNode* invertTree(struct TreeNode* root){
    if(root == NULL)return root;
Swap(&root->left, &root->right);
    // struct TreeNode *t = root->right;
    // root->right = root->left;
    // root->left = t;
    invertTree(root->right);
    invertTree(root->left);
    return root;
}

非递归算法： 

 
 
struct TreeNode* invertTree(struct TreeNode* root){
    if(root == NULL)return root;
    
     struct TreeNode *p = root;
    struct TreeNode *stack[110];
    int top = 0;
    stack[top++] = root;
    while(top!=0){
        p = stack[top-1];
        top--;
        struct TreeNode *t = p->left;
        p->left = p->right;
        p->right = t;      
        if(p->right)
        stack[top++] = p->right;
        if(p->left)
        stack[top++] = p->left;
    }
    return root;
}

101. 对称二叉树 

思路：分成左右两棵树来比较节点是否相等，左边的外侧与右边的外侧比，左边的内侧与右边的内侧比；但在判断节点数值是否相等前，应注意节点为空的情况；若左、右节点任意一个为空，或者都不为空但是数值不同，都是不对称；若都为空，反而是对称的情况 ！！如果对称且不为空，则继续比较左边的左边的外侧与右边的右边的外侧......左边的左边的内侧与右边的右边的内侧......

bool compare(struct TreeNode *left, struct TreeNode *right){
        if(left == NULL && right == NULL)return true;
        else if(left == NULL && right != NULL)return false;
        else if(left != NULL && right == NULL)return false;
        else if(left->val != right->val)return false;
        else
        {
            bool out = compare(left->left, right->right);
            bool in = compare(left->right, right->left);
            return in && out;
        }
    }
 
bool isSymmetric(struct TreeNode* root){
    if(root == NULL)return root;
    return compare(root->left,root->right);
}