leetcode二叉树相关题目复习（C语言版）

目录

1.单值二叉树

2.相同的树

3.对称二叉树

4.二叉树的前序遍历

5.另一颗树的子树

---

1.单值二叉树

思路1：

判断根节点、左节点与右节点的值是否相等，因为正向判断（即判断三值相等返回true）比较麻烦（不能根节点满足条件直接返回true，还需进行左右子树的判断），因此可以通过正难则反的思想，判断哪些情况不是单值二叉树

最后的返回值应该是整棵树根节点，左右子树进行相与操作（即&&）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isUnivalTree(struct TreeNode* root) {if(root == NULL) return true;if(root->left && root->left->val!=root->val) return false;if(root->right && root->right->val!=root->val) return false;return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

思路2：

把根节点的值作为判断标准，遍历整棵树进行判断

代码将会使用前序遍历的方法进行判断

鉴于使用bool类型的函数来完成前序遍历比较难，此处可以使用一个判断标志，在传参时把判断标志的地址一起传过去

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/void PrevOrder(struct TreeNode* root ,int val, int* pa)
{if (root == NULL){return;}if(root->val!=val){*pa=0;}PrevOrder(root->left,val,pa);PrevOrder(root->right,val,pa);return;
}bool isUnivalTree(struct TreeNode* root) {int a=1;PrevOrder(root,root->val,&a);if(a){return true;}else{return false;}
}

2.相同的树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *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);
}

代码重点讲解：

以左右子树为判断的依据，因此最后返回的是isSameTree(p->left,q->left)&&isSameTree(p->right,q->right)；此时可能会担心一个问题，根节点会不会判断？肯定会判断的，如果根节点在前面一条语句 if(p->val != q->val) return false; 没有返回false说明是true，最后通过递归调用语句返回的也还是原来结果

分为以下3种情况：

1.两者皆空

2.只有一个为空：p==NULL||q==NULL 通过或运算，两者皆空在前面已经判断掉了，因此此处可以这么写

3.两者都不为空：如果根节点相同了，但左子树或右子树不同，最后还是会返回true；因此继续使用正难则反的思想，判断不相同的情况；这样左右子树即使都为true，根节点不对依旧会返回false

3.对称二叉树

对称二叉树的根节点怎么样不会影响最终结果，因此就是去判断整棵树根节点的左右子树（假设看作a、b子树）是否对称就行

判断对称的办法：和判断相同类似，唯一的区别在于递归调用时，左子树和右子树进行比较，右子树和左子树进行比较（这边的左右子树指的是a、b子树的根节点后面所连接的左右子树） 

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/bool isSymmetricTree(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 isSymmetricTree(p->left,q->right)&&isSymmetricTree(p->right,q->left);
}bool isSymmetric(struct TreeNode* root) {return isSymmetricTree(root->left,root->right);
}

4.二叉树的前序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}void prevOrder(struct TreeNode* root,int* a,int* pi)
{if(root==NULL) return;a[(*pi)++] = root->val;prevOrder(root->left,a,pi);prevOrder(root->right,a,pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {int size;*returnSize = size = TreeSize(root);int* a = (int*)malloc(sizeof(int)*size);int i=0;prevOrder(root,a,&i);return a;
}

代码重点讲解：

int* returnSize ：leetcode特色，代表的是返回的数组大小；因为数组创建这一步是在函数中由做题者完成，因此最后返回时，也需要有个数组大小；此处传来的是指针，因此直接解引用后赋值即可（leetcode的main函数逻辑如下）

int main()
{//……int n = 0;preorderTraversal(root,n);//……
}

代码重点讲解：

prevOrder(root,a,i)：为什么最后的 i 要传其地址？

i 代表的是数组下标，若不传其地址，那么形参的改变不会致使实参的改变；此时，在递的过程中，i 依然会不断地变大；但在归的过程中，i 会回到原来那个函数的大小，此时 i 下标又被传给了prevOrder(root->right)，这样 i 坐标就被新值覆盖掉了。综上所述，我们需要传递i的地址，让每一次i的变化能影响到每一层递归调用的函数。

下图为图像解释

5.另一颗树的子树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//两者皆空if(p==NULL&&q==NULL) return true;//其中一个为空，一个不为空if(p==NULL||q==NULL) return false;//两者都不为空，如果根节点相同了，但左子树或右子树不同，最后还是会返回true；因此继续使用正难则反的思想，判断不相同的情况；这样左右子树即使都为true，根节点不对依旧会返回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(root->val == subRoot->val && isSameTree(root,subRoot)) return true;return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

代码重点讲解：

只要左右子树中，有一个是满足条件的，就可以返回true，因此最终返回isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot)

当左右子树的根节点相等时，可以通过判断以改根节点为子树的与subRoot是否相等，来判断在整棵树中是否存在subRoot一样的树

当左右子树为空时，因为subRoot的结点个数范围为[1,1000]，因此直接返回false即可