二叉树（LeetCode）

个人主页：
流年如梦

专栏：
《零基础轻松入门C语言》
《数据结构：从入门到掌握》

文章目录

• 一.相同的树
• 二.对称二叉树
• 三.另一棵树的子树
• 四.二叉树的构建及遍历

一.相同的树

👉点击转跳

原题：

参考代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if (p == NULL && q == NULL) return true;
if (p == NULL || q == NULL) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

🧐思路：先判断根节点是否都为空（相同），或其中一个为空（不同），再判断当前节点值是否相等，最后递归判断左右子树是否分别相同

二.对称二叉树

👉点击转跳

原题：

参考代码：

bool isMirror(struct TreeNode* left, struct TreeNode* right) {
if (left == NULL && right == NULL) return true;
if (left == NULL || right == NULL) return false;
if (left->val != right->val) return false;
return isMirror(left->left, right->right) && isMirror(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root) {
if (root == NULL) return true;
return isMirror(root->left, root->right);
}

🧐思路：

1）两个节点都为空 –> 镜像 2）一个为空、一个不为空 –> 不镜像 3）节点值不同 –> 不镜像 4）递归判断左节点的左孩子和右节点的右孩子，以及左节点的右孩子和 右节点的左孩子是否互为镜像

三.另一棵树的子树

👉点击转跳

原题：

参考代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if (p == NULL && q == NULL) return true;
if (p == NULL || q == NULL) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
if (root == NULL) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

🧐思路：定义辅助函数isSameTree，判断两棵树是否完全相同；递归遍历root的每个节点，判断以该节点为根的子树是否和subRoot相同

四.二叉树的构建及遍历

👉点击转跳

原题：

参考代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

//构建二叉树（全局指针记录当前读取位置）
TreeNode* buildTree(const char **s) {
if (**s == '#' || **s == '\\0') {
(*s)++;
return NULL;
}
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = **s;
(*s)++;
node->left = buildTree(s);
node->right = buildTree(s);
return node;
}
//中序遍历
void inorder(TreeNode* root) {
if (root == NULL) return;
inorder(root->left);
printf("%c ", root->val);
inorder(root->right);
}
//释放内存
void freeTree(TreeNode* root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}

int main() {
char s[101];
while (scanf("%s", s) != EOF) {
const char *p = s;
TreeNode* root = buildTree(&p);
inorder(root);
printf("\\n");
freeTree(root);
}

return 0;
}

🧐思路：构建二叉树，用递归方式读取字符串，遇到#代表空树，否则创建节点并递归构建左右子树；再中序遍历（左根右）