二叉树OJ淬体

例1：单值二叉树

题目

bool isUnivalTree(struct TreeNode* root){    //空树直接就是单值    if(!root)        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：二叉树的前序遍历

题目

//我们先把二叉树的节点个数求出来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){    //我们知道二叉树节点个数就好开辟数组大小了    int size =  BinaryTreeSize(root);    int* a = (int*)malloc(sizeof(int)*size);    //我们直接递归preorderTraversal它，是不好递归的因为每次递归你都开辟一个数组吗，不现实    //我们应该递归他的类似性质的函数，不过不可以次次开辟数组，应该传递数组再给一个下标    int i = 0;    _preorderTraversal(root,a,&i);    *returnSize = size;    return a;}

例3：二叉树的中序遍历

题目

 //二叉树节点个数函数int BinaryTreeSize(struct TreeNode* root){    if(!root)        return 0;    return BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;}//子函数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){    //把节点个数赋给数组大小    int size = BinaryTreeSize(root);    //创建合适的数组    int* a = (int*)malloc(sizeof(int)*size);    int i = 0;    _inorderTraversal(root,a,&i);    *returnSize = size;    return a;}

例4：二叉树的后序遍历

题目

//二叉树int BinaryTreeSize(struct TreeNode* root){    return root == NULL ? 0 : BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;}//子函数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){    //数组大小传过来    int size = BinaryTreeSize(root);    //创建合适的数组    int* a = (int*)malloc(sizeof(int)*size);    int i = 0;    _postorderTraversal(root,a,&i);    *returnSize = size;    return a;}

例5：相同的树

题目

bool isSameTree(struct TreeNode* p, struct TreeNode* q){    //都为空    if(!p && !q)        return true;    //有且只有一个是空    if(!p || !q)        return false;    //没有空树    if(p->val != q->val)        return false;    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);}

例6：对称二叉树

题目

bool _isSymmetricTree(struct TreeNode* root1,struct TreeNode* root2){    //两个都是空就返回真    if(!root1 && !root2)        return true;    //只有一个空直接假    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){    //空树就是对称    if(!root)        return true;    //返回他们判断结果     return _isSymmetricTree(root->left,root->right);}

例7：另一棵树的子树

题目

 //判断是否是相同的树bool isSameTree(struct TreeNode* p, struct TreeNode* q){    //都为空    if(!p && !q)        return true;    //有且只有一个是空    if(!p || !q)        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)        return false;    if(isSameTree(root,subRoot))        return true;    return isSubtree(root->left,subRoot)        || isSubtree(root->right,subRoot); }

例8：二叉树遍历

题目

#include <stdio.h>#include <stdlib.h>//树节点typedef struct BinaryTreeNode{    struct BinaryTreeNode* right;    struct BinaryTreeNode* left;    int val;}BTNode;//创建树BTNode* CreateTree(char* str,int* pi){    //#就返回空    if(str[*pi] == '#')    {        (*pi)++;        return NULL;    }    //不是空开始建树    BTNode* root = (BTNode*)malloc(sizeof(BTNode));    root->val = str[(*pi)++];    //递归创建    root->right = CreateTree(str,pi);    root->left = CreateTree(str,pi);    return root;}//中序遍历void InOrder(BTNode* root){    //空就返回    if(!root)        return;    //先走左    InOrder(root->right);    //打印中    printf("%c ",root->val);    //再走右    InOrder(root->left);}int main(){    //因为不超过100    char str[100] = {0};    //多组输入    while(scanf("%s",str) != EOF)    {        //创建树        int i = 0;        BTNode* root = CreateTree(str,&i);        InOrder(root);    }        return 0;}