二叉树算法练习day.2

102.二叉树的层序遍历

链接：. - 力扣（LeetCode）

题目描述：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

思路：

使用队列来实现，先将当前层的节点存储到队列中，并记录当前层的节点的数量，再根据当前层节点的数量将当前层的元素弹出，因此队列中的元素是在不断变化的，需要根据每一层的节点数量情况来选择弹出的元素

代码实现：

/**
 * 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().
 */
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    //二维数组，用来存放每一层的元素
    int **res = malloc(sizeof(int *)*2000);
    //记录层数
    int k = 0;

    *returnColumnSizes = malloc(sizeof(int) *2000);

    //队列，用来保存遍历过的节点
    struct TreeNode **queue = malloc(sizeof(struct TreeNode *)*2000);
    int head = 0, tail = 0;

    *returnSize = 0;

    if(root == NULL)
        return res;

    //根节点不为空，则根节点入队列
    queue[tail++] = root;
    //队列不为空
    while(head != tail)
    {
        //记录每一层的元素个数
        int size = tail - head;
        //存储每一层的元素
        int *num = malloc(sizeof(int) *size);

        for(int i = 0; i < size; i++)
        {
            //队列头元素出队列
            struct TreeNode *node = queue[head++];
            num[i] = node->val;

            //出队列的节点的左右子树不为空，则入队列
            if(node->left != NULL)
                queue[tail++] = node->left;
            if(node->right != NULL)
                queue[tail++] = node->right;
        }
        
        (*returnColumnSizes)[k] = size;
        res[k++] = num;
    }
    *returnSize = k;
    return res;
}

226.翻转二叉树

链接：. - 力扣（LeetCode）

题目描述：

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

思路：两两交换左右孩子节点的指针

使用递归函数实现

1.先确定函数的参数和返回值，此时函数应该传入的是根节点，返回的应该也是根节点

2.确定递归终止的条件，这里的递归终止条件应该是节点为空

3.函数的处理逻辑，此时是交换节点的左右孩子

如果此时使用前序遍历，那么应该先遍历根节点，再依次访问左右子树

如果使用的是后序遍历，那么应该先遍历左右子树，再访问根节点

前序遍历代码(中左右)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    //当前节点为空
    if(!root)
        return root;
    
    //实现节点交换
    struct TreeNode *node;
    node = root->left;
    root->left = root->right;
    root->right = node;

    //遍历左右子树
    invertTree(root->left);
    invertTree(root->right);

    return root;
}
后序遍历代码（左右中）
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    if(!root)
        return root;
    invertTree(root->left);
    invertTree(root->right);

    struct TreeNode *node = root->left;
    root->left = root->right;
    root->right = node;
    
    return root;
}
注意：上述代码不能用于中序遍历，因此会导致右子树一直没有处理（更改之后又会进行一次更改，导致处理的还是原来的左子树）

中序代码（左右中）
入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。

101.对称二叉树

链接：. - 力扣（LeetCode）

题目描述：

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

思路：

主要判断根节点的左右子树是否相等，而不是判断当前节点的左右子树是否相等

使用后序遍历二叉树，因为我们要将左右孩子的信息进行收集并返回给根节点，这样才能进行判断该二叉树是否能够翻转（对称）

递归函数实现：

1.确定函数的参数和返回值，判断真假返回值应该为bool类型，要比较左右子树，应该传入的参数就为两个结构体类型的指针

2.确定函数终止条件，即函数左空右不空，返回假，右空左不空，返回假，左右都为空，返回真，左右不为空但是值不相等，返回假

3.确定函数处理逻辑，当两个节点都不为空，并且两个节点的值相等，比较左子树的左节点和右子树的右节点以及左子树的右节点和右子树的左节点
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool fuc(struct TreeNode *left , struct TreeNode *right)
{
    if(left != NULL && right == NULL) //左空右不空
        return false;
    else if(left == NULL && right != NULL) //右空左不空
        return false;
    else if(left == NULL && right == NULL) //左右都为空
        return true;
    else if(left->val != right->val) //左右值不相等
        return false;
    //值相等并且比较左子树的左节点和右子树的右节点，已经左子树的右节点和右子树左节点
    return (left->val == right->val)&&fuc(left->left,right->right)&&fuc(left->right,right->left);
    
}

bool isSymmetric(struct TreeNode* root) {
    if(!root)
        return true;
    return fuc(root->left,root->right);    
    
}