二叉树OJ题目

前言

总体上看，二叉树题目方面运用到达递归的情况较多。所以在做题目之前，可以将函数递归部分先行复习。

一.单值二叉树

leetcode题目链接：单值二叉树

算法逻辑

1. 空节点处理：如果当前节点 root 为空，直接返回 true。因为空树可以被视为单值二叉树，这是递归的终止条件之一。
2. 左子节点检查：如果当前节点有左子节点（root->left 不为空），并且当前节点的值（root->val）与左子节点的值（root->left->val）不同，那么直接返回 false。因为单值二叉树要求所有节点值相同，一旦发现不同值，就可以确定该树不是单值二叉树。
3. 右子节点检查：类似地，如果当前节点有右子节点（root->right 不为空），并且当前节点的值与右子节点的值不同，也直接返回 false。
4. 递归检查子树：如果当前节点的值与左子节点和右子节点的值都相同，那么继续递归检查左子树和右子树。只有当左子树和右子树都是单值二叉树时，整个树才是单值二叉树。因此，函数返回 isUnivalTree(root->left) && isUnivalTree(root->right)。

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

二.相同的树

leetcode题目链接： 相同的树

算法逻辑

1. 空节点处理：
   如果两个节点 p 和 q 都为空（p == NULL && q == NULL），返回 true。因为空树被认为是相同的，这是递归的终止条件之一。
   如果其中一个节点为空而另一个不为空（p == NULL || q == NULL），返回 false。因为一个空树和一个非空树不可能相同。
2. 节点值比较：
   如果两个节点都不为空，但它们的值不同（p->val != q->val），返回 false。因为两棵相同的树在相同位置上的节点值必须相同。
3. 递归检查子树：
   如果两个节点的值相同，继续递归检查它们的左子树和右子树。只有当左子树和右子树都相同（isSameTree(p->left, q->left) && isSameTree(p->right, q->right)）时，整个树才相同。

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);}

三.对称二叉树

leetcode题目链接：对称二叉树

算法逻辑解析

1. isSameTree 函数
   这个函数用于判断两棵二叉树是否镜像对称，而不是简单的相同。其逻辑如下：

• 空节点处理：
  如果两个节点 p 和 q 都为空（p == NULL && q == NULL），返回 true。因为空树被认为是镜像对称的。
  如果其中一个节点为空而另一个不为空（p == NULL || q == NULL），返回 false。因为一个空树和一个非空树不可能镜像对称。
• 节点值比较：
  如果两个节点都不为空，但它们的值不同（p->val != q->val），返回 false。因为镜像对称的树在相同位置上的节点值必须相同。
• 递归检查子树：
  如果两个节点的值相同，继续递归检查它们的子树。但与判断两棵树是否相同不同的是，这里需要检查的是 p 的左子树和 q 的右子树是否镜像对称，以及 p 的右子树和 q 的左子树是否镜像对称。因此，递归调用为 isSameTree(p->left, q->right) && isSameTree(p->right, q->left)。

2. isSymmetric 函数
   如果根节点为空（root == NULL），返回 true。因为空树是对称的。
   否则，调用 isSameTree 函数，传入根节点的左子树和右子树。如果左子树和右子树镜像对称，则整棵树是对称的。

 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->right)&&isSameTree(p->right,q->left);}
bool isSymmetric(struct TreeNode* root) {if(root == NULL)return true;return isSameTree(root->left,root->right);}

四.另一棵树的子树

leetcode题目链接：另一棵树的子树

算法逻辑解析

1. isSameTree 函数

• 空节点处理：
  如果两个节点 p 和 q 都为空（p == NULL && q == NULL），返回 true。因为空树被认为是相同的。
  如果其中一个节点为空而另一个不为空（p == NULL || q == NULL），返回 false。因为一个空树和一个非空树不可能相同。
• 节点值比较：
  如果两个节点都不为空，但它们的值不同（p->val != q->val），返回 false。因为相同的树在相同位置上的节点值必须相同。
• 递归检查子树：
  如果两个节点的值相同，继续递归检查它们的左子树和右子树。只有当左子树和右子树都相同（isSameTree(p->left, q->left) && isSameTree(p->right, q->right)）时，整个树才相同。

2. isSubtree 函数

• 空树处理：
  如果 subRoot 为空（subRoot == NULL），返回 true。因为空树被认为是任何树的子树。
  如果 root 为空但 subRoot 不为空（root == NULL），返回 false。因为非空树不能是空树的子树。
• 相同树检查：
  如果当前 root 和 subRoot 是相同的树（isSameTree(root, subRoot)），直接返回 true。
• 递归检查子树：
  如果当前 root 和 subRoot 不相同，继续递归检查 root 的左子树和右子树是否包含 subRoot。即返回 isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot)。

 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(subRoot == NULL)return true;if(root == NULL)return false;if(isSameTree(root,subRoot)){return true;}return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

五.二叉树的遍历

牛客链接：二叉树的遍历

1. buyNode 函数

• 功能：创建一个新的二叉树节点。
• 参数：char x，节点存储的数据。
• 返回值：返回一个指向新创建的二叉树节点的指针。
• 逻辑：
  使用 malloc 分配内存空间，创建一个新的 BTnode。
  将节点的 data 设置为传入的字符 x。
  将节点的左右子节点指针初始化为 NULL。
  返回新创建的节点指针。

2. creatTree 函数

• 功能：根据先序序列构建二叉树。
• 参数：
  char* arr：存储先序序列的字符数组。
  int* pi：指向当前处理的字符索引的指针。
• 返回值：返回构建好的二叉树的根节点。
• 逻辑：
  如果当前字符是 #，表示当前节点为空，递归返回 NULL，并将索引 pi 加1。
  如果当前字符不是 #，创建一个新的节点，将当前字符赋值给节点的 data，并将索引 pi 加1。
  递归构建左子树和右子树，并将它们分别赋值给当前节点的 left 和 right。
  返回当前节点。

3. inorder 函数

• 功能：中序遍历二叉树。
• 参数：BTnode* root，二叉树的根节点。
• 返回值：无。
• 逻辑：
  如果当前节点为空，直接返回。
  递归遍历左子树。
  打印当前节点的数据。
  递归遍历右子树。

#include <stdio.h>
#include<stdlib.h>
typedef struct BTnode{char data;struct BTnode* left;struct BTnode* right;
}BTnode;
BTnode* buynode(char x)
{BTnode* ptree = (BTnode*)malloc(sizeof(BTnode));ptree->data = x;ptree->left = ptree->right = NULL;   return ptree;
}
BTnode* creatTree(char* arr, int* pi)
{if(arr[*pi] == '#'){(*pi)++;return NULL;}BTnode* root = buynode(arr[*pi]);(*pi)++;root->left = creatTree(arr,pi);root->right = creatTree(arr,pi);return root;
}
void inorder(BTnode* root)
{if(root == NULL){return;}inorder(root->left);printf("%c ",root->data);inorder(root->right);
}
int main() {char arr[100];scanf("%s",arr);int i = 0;BTnode* root = creatTree(arr,&i);inorder(root);
}