Oj小记：关于二叉树题一二
二叉树遍历
前序遍历:
题目描述
实例：
解题思路：
这道要我们返回这棵二叉树的前序遍历的结果，我们可以用一个数组将它的返回结果保存下来，题目也要求我们返回的是一个数组，以就构建一个数组，大小就为二叉树结点个数
那我们就需要先求二叉树的结点数
然后构建二叉树结点个数大小的数组
然后用前序遍历将二叉树的值传入数组中
最后返回数组就可以了
代码如下：
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;
(*pi)++;
preorder(root->left,arr,pi);
preorder(root->right,arr,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=TreeSize(root);//求二叉树中结点个数
int i=0;
int* arr=(int*)malloc(sizeof(int)*(*returnSize));//开二叉树节点个数的空间给数组
preorder(root,arr,&i);//前序遍历将二叉树结点值插入数组中
return arr;//返回数组
}中序遍历:94. 二叉树的中序遍历 - 力扣（LeetCode）
这道题的解题思路和前序遍历差不多
代码如下：
typedef struct TreeNode TreeNode;
int TreeSize(TreeNode* root)
{
if(root==NULL)
{
return 0;
}
return 1+TreeSize(root->left)+TreeSize(root->right);
}
void InOrder(TreeNode* root,int* arr,int* pi)
{
if(root==NULL)
{
return;
}
InOrder(root->left,arr,pi);
arr[*pi]=root->val;
(*pi)++;
InOrder(root->right,arr,pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=TreeSize(root);
int* arr=(int*)malloc(sizeof(int)*(*returnSize));
int i=0;
InOrder(root,arr,&i);
return arr;
}后序遍历:145. 二叉树的后序遍历 - 力扣（LeetCode）
解题思路和前两道题差不多，就不多赘述
代码为：
typedef struct TreeNode TreeNode;
int TreeSize(TreeNode* root)
{
if(root==NULL)
{
return 0;
}
return 1+TreeSize(root->left)+TreeSize(root->right);
}
void PostOrder(TreeNode* root,int* arr,int* pi)
{
if(root==NULL)
{
return;
}
PostOrder(root->left,arr,pi);
PostOrder(root->right,arr,pi);
arr[*pi]=root->val;
(*pi)++;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=TreeSize(root);
int* arr=(int*)malloc(sizeof(int)*(*returnSize));
int i=0;
PostOrder(root,arr,&i);
return arr;
}单值二叉树：965. 单值二叉树 - 力扣（LeetCode）
解题思路：
这道题就是要比较每个结点的值，其实就分为根结点和左孩子结点的比较、根结点和右孩子结点的比较，比完这两步就不需要再比较左孩子结点和右孩子结点
要注意的是：当结点为空要返回空
代码为：
//根结点 : 左孩子结点
//根结点 : 右孩子结点
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);
}相同的树：100. 相同的树 - 力扣（LeetCode）
解题思路：
这道题要考虑的情况比较多:
当两个树的结点都为空，就返回真；当其中有一棵树的结点不为空，就返回假；
当它们的结点的值相等就返回真。
遍历的步骤为：先分别遍历两棵树的左子树结点，再遍历右子树结点，只有两棵树的结点都相等的情况下，才表示两棵树相同
代码为：
/*
先遍历左子树，再遍历右子树
要保证两棵子树的值都相等
才能返回真
*/
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);
}另一棵树的子树572. 另一棵树的子树 - 力扣（LeetCode）
解题思路：
这道题要用到前一题的思路，又因为这道题是求是否为另一棵树的子树，所以还要多考虑几种情况：
当其中一颗树为空就返回假；
两棵树的比较，只要左右子树其中一棵和另外一棵树相同就为真
代码为：
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(root==NULL)
{
return false;
}
if(isSameTree(root,subRoot))
{
return true;
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}对称二叉树101. 对称二叉树 - 力扣（LeetCode）
解题思路
这道题和相同的树这道题的解题思路没什么区别，就需要注意的是：它的对比的是左子树的左孩子和右子树的右孩子
代码为：
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(isSameTree(root->left,root->right))
{
return true;
}
return false;
}