文章目录
一、965. 单值二叉树
1、题目描述
2、题目代码
写法一：
/** * 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);
}
写法二：
bool _isUnivalTree(struct TreeNode* root, int val){
if(root == NULL)
return true;
if(root->val != val)
return false;
return _isUnivalTree(root->left, val)
&& _isUnivalTree(root->right, val);
}
bool isUnivalTree(struct TreeNode* root){
if(root == NULL)
return true;
int val = root->val;
return _isUnivalTree(root, val);
}
二、144. 二叉树的前序遍历
1、题目描述
2、题目代码
/** * 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 pTSize(struct TreeNode* root)
{
return (root==NULL) ? 0 : pTSize(root->left) + pTSize(root->right) + 1;
}
void _preorderTraversal(struct TreeNode* root,int*a ,int* pi )
{
if(root == NULL)
return;
a[(*pi)++] = root->val;
_preorderTraversal(root->left , a, pi);
_preorderTraversal(root->right , a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
int size = pTSize(root);
int* a = (int*)malloc(sizeof(int) * size);
*returnSize = size;
int i=0;
_preorderTraversal(root , a ,&i );
return a;
}
三、104. 二叉树的最大深度
1、题目描述
2、题目代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int maxDepth(struct TreeNode* root){
if(root == NULL)
return 0;
int lenghleft = maxDepth(root->left) + 1;
int lenghright = maxDepth(root->right) + 1;
return (lenghleft > lenghright) ? lenghleft : lenghright;
}
四、226. 翻转二叉树
1、题目描述
2、题目代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
void swap(struct TreeNode** px,struct TreeNode** py)
{
struct TreeNode* tmp = *px;
*px = *py;
*py = tmp;
}
struct TreeNode* invertTree(struct TreeNode* root){
if(root == NULL)
return root;
swap(&root->left,&root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
3、方便理解的图
五、94. 二叉树的中序遍历
1、题目描述
2、题目代码
/** * 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 iTSize(struct TreeNode* root)
{
return (root == NULL) ? 0 : iTSize(root->left) + iTSize(root->right) + 1;
}
void _inorderTraversal(struct TreeNode* root,int* a,int* pi)
{
if(root == NULL)return;
_inorderTraversal(root->left,a,pi);
a[(*pi)++] = root->val;
_inorderTraversal(root->right,a,pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
int size = iTSize(root);
int* a = (int*)malloc(sizeof(int) * size);
*returnSize = size;
int i = 0;
_inorderTraversal( root, a, &i);
return a;
}
六、145. 二叉树的后序遍历
1、题目描述
2、题目代码
/** * 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 pTSize(struct TreeNode* root)
{
return (root == NULL) ? 0 : pTSize(root->left) + pTSize(root->right) + 1;
}
void _postorderTraversal(struct TreeNode* root,int* a,int* pi)
{
if(root == NULL)return;
_postorderTraversal(root->left,a,pi);
_postorderTraversal(root->right,a,pi);
a[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
int size = pTSize(root);
int* a = (int*)malloc(sizeof(int) * size);
*returnSize = size;
int i = 0;
_postorderTraversal( root, a, &i);
return a;
}
七、100. 相同的树
1、题目描述
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);
}
八、KY11 二叉树遍历
1、题目描述
2、题目代码
#include<stdio.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
BTNode* createBT(char* a, int* pi)
{
if(a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->_data = a[*pi];
(*pi)++;
root->_left = createBT( a, pi);
root->_right = createBT( a, pi);
return root;
}
void inOrderBT(BTNode* root)
{
if(root == NULL)
{
return;
}
inOrderBT(root->_left);
printf("%c ",root->_data);
inOrderBT(root->_right);
}
int main()
{
char a[100];
while(scanf("%s",a) != EOF)
{
int i = 0;
BTNode* root = createBT(a , &i);
inOrderBT(root);
}
return 0;
}
九、110. 平衡二叉树
1、题目描述
2、题目代码
写法一：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int BinaryTreeDepth(struct TreeNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDepth = BinaryTreeDepth(root->left);
int rightDepth = BinaryTreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
bool isBalanced(struct TreeNode* root){
if(root == NULL)
return true;
int leftDepth = BinaryTreeDepth(root->left);
int rightDepth = BinaryTreeDepth(root->right);
if(abs(leftDepth-rightDepth)>1)
return false;
return isBalanced(root->left) && isBalanced(root->right);
}
写法二：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int maxDepth(struct TreeNode* root){
return root ? 1 + fmax(maxDepth(root->left) , maxDepth(root->right)) : 0;
}
bool isBalanced(struct TreeNode* root){
if(root == NULL)
return true;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return abs(left - right) < 2
&& isBalanced(root->left)
&& isBalanced(root->right);
}
十、572. 另一棵树的子树
1、题目描述
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);
}
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. 对称二叉树
1、题目描述
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->right) && isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root){
if(root == NULL)
return true;
return isSameTree(root->left,root->right);
}
以上是本篇文章的全部内容，如果文章有错误或者有看不懂的地方，多和喵博主交流。互相学习互相进步。如果这篇文章对你有帮助，可以给喵博主一个关注，你们的支持是我最大的动力。
文章评论