二叉树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：二叉树遍历

题目