This is the 22nd day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”
Binary tree OJ quench body
Case 1:Single-valued binary tree
The title
image-20211114094938096
image-20211114100001843
bool isUnivalTree(struct TreeNode* root){
// An empty tree is a single value
if(! root)return true;
// If there is only one left node
if(root->left && root->left->val ! = root->val)return false;
// If there is only one right node
if(root->right && root->right->val ! = root->val)return false;
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
Copy the code
Example 2:Antecedent traversal of binary trees
The title
image-20211114101027475
image-20211114211340327
// Let's find the number of nodes in the binary tree
int BinaryTreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
}
void _preorderTraversal(struct TreeNode* root,int* a,int* i)
{
if(! root)return;
a[(*i)++] = root->val;
_preorderTraversal(root->left,a,i);
_preorderTraversal(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
// We know the number of nodes in the binary tree
int size = BinaryTreeSize(root);
int* a = (int*)malloc(sizeof(int)*size);
// We recurse preorderTraversal directly which is not very recursive because every time you recurse you open up an array? Not realistic
// We should recurse to a function of similar properties, but instead of opening an array each time, we should pass the array with a lower index
int i = 0;
_preorderTraversal(root,a,&i);
*returnSize = size;
return a;
}
Copy the code
Example 3:Middle order traversal of binary trees
The title
image-20211116214530749
image-20211116214359131
// Binary tree node number function
int BinaryTreeSize(struct TreeNode* root){
if(! root)return 0;
return BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
}
/ / function
void _inorderTraversal(struct TreeNode* root,int* a,int* pi){
if(! root)return;
_inorderTraversal(root->left,a,pi);
a[(*pi)++] = root->val;
_inorderTraversal(root->right,a,pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
// Assign the number of nodes to the array size
int size = BinaryTreeSize(root);
// Create the appropriate array
int* a = (int*)malloc(sizeof(int)*size);
int i = 0;
_inorderTraversal(root,a,&i);
*returnSize = size;
return a;
}
Copy the code
Example 4:Backward traversal of a binary tree
The title
image-20211116214847981
image-20211116221210027
/ / binary tree
int BinaryTreeSize(struct TreeNode* root){
return root == NULL ? 0 : BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
}
/ / function
void _postorderTraversal(struct TreeNode* root,int* a,int* pi){
if(! root)return;
_postorderTraversal(root->left,a,pi);
_postorderTraversal(root->right,a,pi);
a[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
// Pass the array size
int size = BinaryTreeSize(root);
// Create the appropriate array
int* a = (int*)malloc(sizeof(int)*size);
int i = 0;
_postorderTraversal(root,a,&i);
*returnSize = size;
return a;
}
Copy the code
Example 5:The same tree
The title
image-20211114214742547
image-20211114233423560
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
/ / is empty
if(! p && ! q)return true;
// One and only one is empty
if(! p || ! q)return false;
// No empty tree
if(p->val ! = q->val)return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
Copy the code
Example 6:Symmetric binary tree
The title
image-20211116072024229
image-20211116073040713
bool _isSymmetricTree(struct TreeNode* root1,struct TreeNode* root2)
{
// Return true if both are null
if(! root1 && ! root2)return true;
// There is only one empty direct false
if(! root1 || ! root2)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){
// Empty trees are symmetric
if(! root)return true;
// Return their judgment
return _isSymmetricTree(root->left,root->right);
}
Copy the code
Example 7:A subtree of another tree
The title
image-20211116074903027
image-20211116202318803
// Check if it is the same tree
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
/ / is empty
if(! p && ! q)return true;
// One and only one is empty
if(! p || ! q)return false;
// No empty tree
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)return false;
if(isSameTree(root,subRoot))
return true;
return isSubtree(root->left,subRoot)
|| isSubtree(root->right,subRoot);
}
Copy the code
Example 8:Binary tree traversal
The title
image-20211118001943031
image-20211118231042018
#include <stdio.h>
#include <stdlib.h>
/ / tree node
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* right;
struct BinaryTreeNode* left;
int val;
}BTNode;
/ / create a tree
BTNode* CreateTree(char* str,int* pi)
{
//# return null
if(str[*pi] == The '#')
{
(*pi)++;
return NULL;
}
// It is not empty to start building
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->val = str[(*pi)++];
// create recursively
root->right = CreateTree(str,pi);
root->left = CreateTree(str,pi);
return root;
}
// middle order traversal
void InOrder(BTNode* root)
{
// return if empty
if(! root)return;
/ / go first to the left
InOrder(root->right);
/ / print
printf("%c ",root->val);
/ / go right
InOrder(root->left);
}
int main(a)
{
// Because it does not exceed 100
char str[100] = {0};
// Multiple input groups
while(scanf("%s",str) ! = EOF) {/ / create a tree
int i = 0;
BTNode* root = CreateTree(str,&i);
InOrder(root);
}
return 0;
}
Copy the code