面试题目：(6)翻转二叉树

题目

• 翻转二叉树 （中间对称翻转，等于镜像）
• 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
• 示例1：
  • 输入：root = [4,2,7,1,3,6,9]
  • 输出：[4,7,2,9,6,3,1]
• 示例1：
  • 输入：root = [2,1,3]
  • 输出：[2,3,1]  
• 示例1：
  • 输入：root = []
  • 输出：[]
• 提示：
  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100
  • * struct TreeNode {
  • *     int val;
  • *     struct TreeNode *left;
  • *     struct TreeNode *right;
  • * };

代码

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};
struct TreeNode * crete_node(int number)
{struct TreeNode *new_node = (struct TreeNode *)malloc(sizeof(struct TreeNode));new_node->val = number;new_node->left = NULL;new_node->right = NULL;return new_node;
}
struct TreeNode * add_tree(struct TreeNode *tree, int number, int count)
{struct TreeNode *new_node = crete_node(number);if (count == 1){tree = new_node;}else{struct TreeNode *current = tree;int position = count;// 找到插入位置,bufor (int i = 1; i < count / 2; i *= 2) {if (position & 1) {if (!current->right) {current->right = new_node;return tree;}current = current->right;} else {if (!current->left) {current->left = new_node;return tree;}current = current->left;}position >>= 1;}if (position & 1) {current->right = new_node;} else {current->left = new_node;}}return tree;}// 层序遍历打印二叉树
void printLevelOrder(struct TreeNode* root) {if (root == NULL) {printf("[]\n");return;}struct TreeNode* queue[100];int front = 0, rear = 0;queue[rear++] = root;printf("[");while (front < rear) {struct TreeNode* node = queue[front++];if (node) {printf("%d", node->val);if (node->left != NULL) queue[rear++] = node->left;if (node->right != NULL) queue[rear++] = node->right;}if (front < rear) printf(", ");}printf("]\n");
}void zhuan_list(struct TreeNode* root)
{if (root == NULL) return;struct TreeNode* temp = root->left;root->left = root->right;root->right = temp;zhuan_list(root->left);zhuan_list(root->right);
}
int main()
{char s[256] ="";printf("root = ");fgets(s,sizeof(s),stdin);s[strcspn(s, "\n")] = '\0';int number = 0;struct TreeNode *tree = NULL;int count = 1;for (int i = 0; i < strlen(s); i++){if (s[i]<= '9' && s[i] >= '0'){number = number * 10 +(s[i] - '0');}else if(s[i] == ',' || s[i] == ']'){tree = add_tree(tree,number,count);count++;number = 0;}}printLevelOrder(tree);zhuan_list(tree);printLevelOrder(tree);return 0;
}

解析

• 接收字符串后去掉换行符
• 遍历字符串，遇到数字保存，遇到"，“和"]"就新建节点组成树
  • 组成树
    • 传入这是第几个节点，进行除于2来找到父节点
    • 通过二进制的最后一位数来决定是左子树还是右子树，一层一层的进入
    • 进入了下一层也就是进入了新节点，判断左子树是否为空先，在判断右子树，哪个为空就进哪一个
    • 但根节点下面的两个数字为2和3，都进入不了for循环，要单独通过最后一位来进行加载
• 打印树
• 翻转树
  • 递归函数翻转
    • 判断是否为空，为空退出
    • 将左右节点翻转
    • 再分别递归进入左右子树进行翻转