【数据结构】二叉树练习

1.单值二叉树

965. 单值二叉树 - 力扣（LeetCode）

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

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;else{int lret=isSameTree(p->left,q->left);int rret=isSameTree(p->right,q->right);return lret&&rret;}
}

3.对称二叉树

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->right,q->left)&&isSameTree(p->left,q->right);
} bool isSymmetric(struct TreeNode* root) {return isSameTree(root->left,root->right);
}

4.前序遍历（返回数组） 

144. 二叉树的前序遍历 - 力扣（LeetCode）

int TreeSize(struct TreeNode* root)
{return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void preorder(struct TreeNode* root,int*a,int*pi)
{if(root==NULL)return;a[(*pi)++]=root->val;preorder(root->left,a,pi);preorder(root->right,a,pi);}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*a=(int*)malloc(sizeof(int)*TreeSize(root));int i=0;preorder(root,a,&i);return a;
}

5.中序遍历（返回数组） 

94. 二叉树的中序遍历 - 力扣（LeetCode）

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}void Inorder(struct TreeNode* root, int*a,int*pi){if(root==NULL)return;Inorder(root->left, a, pi);a[(*pi)++] = root->val;Inorder(root->right, a, pi);}int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*a=(int*)malloc(sizeof(int)*TreeSize(root));int i=0;Inorder(root,a,&i);return a;
}

 6.后序遍历（返回数组）

145. 二叉树的后序遍历 - 力扣（LeetCode）

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}void postorder(struct TreeNode* root, int*a,int*pi){if(root==NULL)return;postorder(root->left, a, pi);postorder(root->right, a, pi);a[(*pi)++] = root->val;}int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*a=(int*)malloc(sizeof(int)*TreeSize(root));int i=0;postorder(root,a,&i);return a;
}

7.另一颗树的子树 

572. 另一棵树的子树 - 力扣（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->right,q->right)&&isSameTree(p->left,q->left);
} bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{if(root==NULL)return false;if(isSameTree(root,subRoot))return true;return isSubtree(root->right,subRoot)||isSubtree(root->left,subRoot);
}

8.二叉树遍历

#include <stdio.h>
#include<stdlib.h>struct TreeNode
{struct TreeNode*right;struct TreeNode*left;char val;
};struct TreeNode*CreatTree(char*a,int*pi)
{if(a[*pi]=='#'){(*pi)++;return NULL;}struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));root->val=a[*pi];(*pi)++;root->left=CreatTree(a,pi);root->right=CreatTree(a,pi);return root;}void Inorder(struct TreeNode* root)
{if(root==NULL)return;Inorder(root->left);printf("%c ",root->val);Inorder(root->right);
}int main() 
{char a[100];scanf("%s",a);int i=0;struct TreeNode* root=CreatTree(a,&i);Inorder(root);return 0;
}