数据结构初阶-二叉树的应用

1.单值二叉树

题目链接：https://leetcode.cn/problems/univalued-binary-tree/description/

题目思路：我们把根结点与左孩子和右孩子进行比较，只有左右子树都是单值二叉树的时候才为单值二叉树。但是我们需要先返回的是false，最后再返回左子树&&右子树的结果。所以代码如下：

 typedef struct TreeNode TreeNode;
bool isUnivalTree(struct TreeNode* root) 
{if(root==NULL){//如果全为空的情况下，没有存储任何值也就是单值二叉树return true;}if(root->left && root->val != root->left->val){//当左孩子不存在时我们仍然返回的是true//root->left是判断是否左子树为空的return false;}if(root->right && root->val !=root->right->val){return false;}return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

2.相同的树

题目链接：https://leetcode.cn/problems/same-tree/description/

题目思路：如果p、q一者为空另一者为非空，则为false，我们使用前序遍历的方法，最终返回p的左子树和q的左子树的返回值&&p的右子树和q的右子树的返回值。

typedef struct TreeNode TreeNode;
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);
}

我们主要是返回的是false,如果我们在第三个if条件下p->val==q->val return true;这样我们不确定之后的树中是否还是相同的情况，只有我们最终比较到两者都为空才行。

*3对称二叉树（扩展）

题目链接：https://leetcode.cn/problems/symmetric-tree/description/

题目思路：由于我们发现这个给出的函数只有一个参数，但是我们需要比较的是左子树的左结点和右子树的右结点的返回值&&左子树的右结点和右子树的左结点的返回值，所以我们需要另外一个函数来判断，思路要把单值二叉树和相同的树进行整合，最终能得到以下代码：

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

4.另一棵树的子树

题目链接：https://leetcode.cn/problems/subtree-of-another-tree/description/

题目思路：我们把第二题的代码全部放入题目后，然后每次都调用这个函数，先递归左子树再递归右子树，并返回二者或的结果，代码如下：

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

5.二叉树的前序遍历

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

题目思路：返回值为int*，我们需要返回数组，数组还必须手动malloc。我们需要先求出二叉树结点的个数，这个函数我们之前写过，就不需要讲解了；然后我们需要malloc结点个数的数据，最后前序遍历，最终代码如下：

typedef struct TreeNode TreeNode;//求二叉树结点个数int TreeSize(TreeNode* root){if(root==NULL){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);}//前序遍历void PreOrder(TreeNode* root,int* arr,int* pi){if(root==NULL){return ;}arr[(*pi)++]=root->val;PreOrder(root->left,arr,pi);PreOrder(root->right,arr,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{//我们需要自己求出结点个数*returnSize=TreeSize(root);int* arr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;//我们需要不断递增下标，所以要传址操作PreOrder(root,arr,&i);return arr;
}

拓展练习，题目链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

和https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

6.二叉树的构建及遍历

该题目难度较难，所以有兴趣的可以去看

题目链接：https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef

题目思路：首先我们需要根据数组来创建二叉树，之前我们是手动来创建二叉树的，所以我们没有注意这个问题，这个题目就可以锻炼我们创建二叉树的技巧。如何根据数组来创建二叉树？只要不为#我们就创建这个结点，第一个不为#的就是根结点，所以我们需要一个创建结点的函数，之前我们写过，所以很简单，然后我们用传址操作来得到每一个结点，先进行根结点的创建，再是左孩子，最后右孩子，最终代码如下：

#include <stdio.h>
//定义结点
typedef struct BinaryTreeNode
{
char data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//创建结点
BTNode* buyNode(char ch)
{BTNode* node=(BTNode*)malloc(sizeof(BTNode));node->data=ch;node->left=node->right=NULL;return node;
}
//创建二叉树
BTNode* createTree(char* arr,int* pi)
{if(arr[*pi]=='#'){(*pi)++;return NULL;}BTNode* root=buyNode(arr[*pi]);++(*pi);root->left=createTree(arr,pi);root->right=createTree(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=createTree(arr, &i);InOrder(root);return 0;
}