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

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

// 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

 // 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

/ / 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

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

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

 // 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

#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