【数据结构】二叉树相关OJ题

一、单值二叉树

单值二叉树

题目描述

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树，只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例

思路分析

一棵树的所有节点都有相同的值，当且仅当对于树上的每一条边的两个端点，它们都有相同的值（这样根据传递性，所有节点都有相同的值）

因此，我们可以对树进行一次深度优先搜索，当搜索到节点root时，我们检查root的左孩子和右孩子是否相同，不相同则返回false,直到检查了所有的节点，所有我们就可以进行递归遍历，每次比较根节点和左右孩子的val值是否相等，不相等就返回false，然后递归比较左子树和右子树。

【注意】我们比较的条件应该是不相等，因为不相等就可以直接返回，而相等还要继续比较

代码实现

bool isUnivalTree(struct TreeNode* root)
{// 根节点为空返回trueif (root == NULL)return true;// 左子树存在但是不相等则返回falseif (root->left && root->val != root->left->val)return false;// 右子树存在但是不相等则返回falseif (root->right && root->val != root->right->val)return false;// 继续递归 左右子树return isUnivalTree(root->left) && isUnivalTree(root->right);
}

二、检查两颗树是否相同

题目链接

检查两颗树是否相同

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例

思路分析

如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同，如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

代码实现

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{// 如果根节点都为NULL则返回tureif (p == NULL && q == NULL)return true;// 运行到这里，都不为空，则下面判断的情况为只有一个为空，另一个不为空，所以返回falseif (p == NULL || q == NULL)return false;// 都不为空但是值不相等返回falseif (p->val != q->val)return false;// 继续比较左右子树return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

三、判断一棵树是否为另一颗树的子树

题目链接

判断一棵树是否为另一颗树的子树

题目描述

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树

示例

思路分析

由于root和subRoot中可能含有一个和多个值相同的节点，所以判断不相等的时候，又要返回原来的根节点，所以我们可以这道题利用上一题的代码，我们的思路为不断的比较root这棵树以每一个节点作为根节点，判断是否和subRoot相等，相等就返回true,所以节点都变量之后都没有相等的树就返回false.

代码实现

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{// 如果根节点都为NULL则返回tureif (p == NULL && q == NULL)return true;// 运行到这里，都不为空，则下面判断的情况为只有一个为空，另一个不为空，所以返回falseif (p == NULL || q == NULL)return false;// 都不为空但是值不相等返回falseif (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);}

四、对称二叉树

题目链接

对称二叉树

题目描述

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

示例

思路分析

这道题和判断两棵树是否相等的思路一致，只是有一些细节有所不同。对称二叉树是最左边和最右边的节点相同，所以我们就可以拿第一棵树的左子树和第二棵树的右子树进行比较，拿第一棵树的右子树和第二棵树的左子树进行比较，不相等就返回false,相等就继续比较，直到所有节点都相等，所以我们就可以对检查两颗是否相同的代码进行修改即可，即对其递归代码中的参数进行调整

return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);

代码实现

//判断两颗子树是否对称
bool isSameTree(struct TreeNode* p,struct TreeNode* q)
{if(p==NULL&&q==NULL){return true;}// 当两棵树中只有一棵树的节点为NULL时，节点数量不相等，直接返回falseif(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){return isSameTree(root->left,root->right);
}

五、二叉树的前序遍历

题目链接

二叉树的前序遍历

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例

思路分析

二叉树的前序遍历我们已经非常熟悉，这里我提出两点需要注意的地方：

1.由于二叉树的节点数是未知的，为了不浪费空间，我们可以先求出二叉树的节点数，然后开辟对应大小的空间

2.由于数据存储在一个数组中，所以我们需要一个变量i来控制数组的下标，由于在递归调用的过程中对形参的改变不会改变影响实参，所以这里我们需要传递i的地址，通过指针来控制i的增长

代码实现

// 计算节点个数
int TreeSize(struct TreeNode* root)
{if (root == NULL)return 0;// 左子树的节点个数+右节点的个数+1return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 前序遍历并存入数组中
void preorder(struct TreeNode* root, int* a, int* pi)
{if (root == NULL)return;// 先遍历根，再访问左子树，左后访问右子树a[*pi] = root->val;(*pi)++;preorder(root->left, a, pi);preorder(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{// 求二叉树的节点个数int size = TreeSize(root);// 开辟同等大小的空间int* a = (int*)malloc(sizeof(int) * size);int i = 0;//前序遍历preorder(root, a, &i);*returnSize = size;return a;
}

六、二叉树中序遍历

题目链接

二叉树中序遍历

题目描述

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例

二叉树的中序遍历和前序遍历一样，只是访问节点的顺序不同

代码实现

// 计算节点个数
int TreeSize(struct TreeNode* root)
{if (root == NULL)return 0;// 左子树的节点个数+右节点的个数+1return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 前序遍历并存入数组中
void inorder(struct TreeNode* root, int* a, int* pi)
{if (root == NULL)return;// 先遍历左子树，再访问根节点，左后访问右子树inorder(root->left, a, pi);a[*pi] = root->val;(*pi)++;inorder(root->right, a, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{// 求二叉树的节点个数int size = TreeSize(root);// 开辟同等大小的空间int* a = (int*)malloc(sizeof(int) * size);int i = 0;//中序遍历inorder(root, a, &i);*returnSize = size;return a;
}

七、二叉树的后序遍历

题目链接

二叉树的后序遍历

题目描述

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例

思路分析

二叉树的后序遍历和前序遍历，中序遍历一样，只是访问节点的顺序不同

代码实现

代码实现

// 计算节点个数
int TreeSize(struct TreeNode* root)
{if (root == NULL)return 0;// 左子树的节点个数+右节点的个数+1return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 后序遍历并存入数组中
void postorder(struct TreeNode* root, int* a, int* pi)
{if (root == NULL)return;// 先遍历左子树，再访问右子树，左后访问根节点postorder(root->left, a, pi);postorder(root->right, a, pi);a[*pi] = root->val;(*pi)++;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{// 求二叉树的节点个数int size = TreeSize(root);int* a = (int*)malloc(sizeof(int) * size);int i = 0;// 后续遍历postorder(root, a, &i);*returnSize = size;return a;
}

八、二叉树的构建及遍历

题目链接

二叉树的构建及遍历

题目描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

示例

思路分析

这道题目是前序建立二叉树和中序遍历，我们写成两个子函数即可，对于二叉树的创建，字符为‘#’说明节点为空，我们直接返回即可，然后依次递归创建节点即可

代码实现

#include <stdio.h>
#include <stdlib.h>// 符号和结构的定义
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;// 构建二叉树
BTNode* BTreeCreate(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}// 创建根节点BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL) {perror("malloc fail");exit(-1);}root->data = a[*pi];(*pi)++;// 创建左子树和右子树root->left = BTreeCreate(a, pi);root->right = BTreeCreate(a, pi);return root;
}
// 二叉树中序遍历
void InOrder(BTNode* root)
{if (root == NULL){return;}// 先访问左子树，再访问根节点，最后访问右子树InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}int main()
{char str[100];scanf("%s", str);// 创建二叉树int i = 0;BTNode* root = BTreeCreate(str, &i);// 二叉树的中序遍历InOrder(root);return 0;
}