Binary tree OJ Quenched body

example 1： Single valued binary trees

subject

bool isUnivalTree(struct TreeNode* root){    // An empty tree is simply a single valued tree     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);}

example 2： Preorder traversal of two tree

subject

// Let's find out the number of nodes of 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){    // If we know the number of binary tree nodes, we can open up the array size     int size =  BinaryTreeSize(root);    int* a = (int*)malloc(sizeof(int)*size);    // We recurs directly preorderTraversal it , It's not easy to recurse, because every time you recurse, you open up an array , Not reality     // We should recurse his functions with similar properties , But you can't open up arrays again and again , You should pass the array to a subscript     int i = 0;    _preorderTraversal(root,a,&i);    *returnSize = size;    return a;}

example 3： Middle order traversal of binary trees

subject

 // Binary tree node number function int BinaryTreeSize(struct TreeNode* root){    if(!root)        return 0;    return BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;}// Subfunctions 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 an appropriate array     int* a = (int*)malloc(sizeof(int)*size);    int i = 0;    _inorderTraversal(root,a,&i);    *returnSize = size;    return a;}

example 4： Postorder traversal of binary trees

subject

// Binary tree int BinaryTreeSize(struct TreeNode* root){    return root == NULL ? 0 : BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;}// Subfunctions 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 an appropriate array     int* a = (int*)malloc(sizeof(int)*size);    int i = 0;    _postorderTraversal(root,a,&i);    *returnSize = size;    return a;}

example 5： Same tree

subject

bool isSameTree(struct TreeNode* p, struct TreeNode* q){    // All is empty     if(!p && !q)        return true;    // There is and only one is empty     if(!p || !q)        return false;    // There is no empty tree     if(p->val != q->val)        return false;    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);}

example 6： Symmetric binary tree

subject

bool _isSymmetricTree(struct TreeNode* root1,struct TreeNode* root2){    // If both are empty, it returns true     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){    // An empty tree is symmetric     if(!root)        return true;    // Return their judgment      return _isSymmetricTree(root->left,root->right);}

example 7： The subtree of another tree

subject

 // Determine whether it is the same tree bool isSameTree(struct TreeNode* p, struct TreeNode* q){    // All is empty     if(!p && !q)        return true;    // There is and only one is empty     if(!p || !q)        return false;    // There is 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); }

example 8： Binary tree traversal

subject

#include <stdio.h>#include <stdlib.h>// Tree node typedef struct BinaryTreeNode{    struct BinaryTreeNode* right;    struct BinaryTreeNode* left;    int val;}BTNode;// Create trees BTNode* CreateTree(char* str,int* pi){    //# Return empty     if(str[*pi] == '#')    {        (*pi)++;        return NULL;    }    // It's not an empty start     BTNode* root = (BTNode*)malloc(sizeof(BTNode));    root->val = str[(*pi)++];    // Recursive create     root->right = CreateTree(str,pi);    root->left = CreateTree(str,pi);    return root;}// In the sequence traversal void InOrder(BTNode* root){    // Empty returns     if(!root)        return;    // Go left first     InOrder(root->right);    // Printing     printf("%c ",root->val);    // Go right again     InOrder(root->left);}int main(){    // Because no more than 100    char str[100] = {0};    // Multi group input     while(scanf("%s",str) != EOF)    {        // Create trees         int i = 0;        BTNode* root = CreateTree(str,&i);        InOrder(root);    }        return 0;}