1.单值二叉树

题目:

力扣https://leetcode.cn/problems/univalued-binary-tree/

思路:

单值二叉树 = root和左右孩子的值相等 + 左子树是单值二叉树 + 右子树是单值二叉树

代码:

/*** 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.相同的树

题目:

力扣https://leetcode.cn/problems/same-tree/submissions/

思路:

相同二叉树 = 比较两棵树的根 + 递归左子树（是否是相同二叉树）+ 递归右子树（是否是相同二叉树）

代码:

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

3.对称二叉树

 题目:

力扣https://leetcode.cn/problems/symmetric-tree/

思路:

解题方法和上一道题相似

原来的函数接口上是递归不起来的，因此要写一个子函数。

代码:

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

4.二叉树的前序遍历

题目:

力扣https://leetcode.cn/problems/binary-tree-preorder-traversal/

思路:

• 计算二叉树的节点个数
• 创建新的数组，数组大小为二叉树总结点大小
• 前序遍历根，左，右

 代码:

/*** 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 _preorderTraversal(struct TreeNode*root,int*a,int*pi)
{if(root==NULL)return;//进行前序遍历根，左，右printf("%d ",root->val);a[(*pi)++]=root->val;_preorderTraversal(root->left,a,pi);_preorderTraversal(root->right,a,pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{int size=TreeSize(root);printf("size:%d\n",size);int*a=malloc(sizeof(int)*size);int i=0;_preorderTraversal(root,a,&i);*returnSize=size;return a;
}

5. 二叉树中序遍历 

题目:

力扣https://leetcode.cn/problems/binary-tree-inorder-traversal/

思路:

• 计算二叉树的节点个数
• 创建新的数组，数组大小为二叉树总结点大小
• 中序遍历左，根，右

代码:

/*** 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 _inorderTraversal(struct TreeNode*root,int*a,int*pi)
{if(root==NULL)return;//进行中序遍历左，根，右printf("%d ",root->val);_inorderTraversal(root->left,a,pi);a[(*pi)++]=root->val;_inorderTraversal(root->right,a,pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize)
{int size=TreeSize(root);printf("size:%d\n",size);int*a=malloc(sizeof(int)*size);int i=0;_inorderTraversal(root,a,&i);*returnSize=size;return a;
}

 6.二叉树后序遍历 

题目:

力扣https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

思路:

• 计算二叉树的节点个数
• 创建新的数组，数组大小为二叉树总结点大小
• 后序遍历左，右，根，

代码:

/*** 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 _postorderTraversal(struct TreeNode*root,int*a,int*pi)
{if(root==NULL)return;//进行中序遍历左，根，右printf("%d ",root->val);_postorderTraversal(root->left,a,pi);_postorderTraversal(root->right,a,pi);a[(*pi)++]=root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize)
{int size=TreeSize(root);printf("size:%d\n",size);int*a=malloc(sizeof(int)*size);int i=0;_postorderTraversal(root,a,&i);*returnSize=size;return a;
}

7.另一颗树的子树

题目:

力扣https://leetcode-cn.com/problems/subtree-of-another-tree/

思路:

 思路: 相同的树+递归左子树+递归右子树

代码: 

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