你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

算法给小码农二叉树OJ淬体

2021-11-18 5:01:38

文章目录

  • 二叉树OJ淬体
    • 例1:[单值二叉树](https://leetcode-cn.com/problems/univalued-binary-tree/)
      • 题目
    • 例2:[二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
      • 题目
    • 例3:[二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
      • 题目
    • 例4:[二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
      • 题目
    • 例5:[相同的树](https://leetcode-cn.com/problems/same-tree/)
      • 题目
    • 例6:[对称二叉树](https://leetcode-cn.com/problems/symmetric-tree/)
      • 题目
    • 例7:[另一棵树的子树](https://leetcode-cn.com/problems/subtree-of-another-tree/)
      • 题目
    • 例8:[二叉树遍历](https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking)
      • 题目

在这里插入图片描述

二叉树OJ淬体

例1:单值二叉树

题目

image-20211114094938096

image-20211114100001843

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:二叉树的前序遍历

题目

image-20211114101027475

image-20211114211340327

//我们先把二叉树的节点个数求出来
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:二叉树的中序遍历

题目

image-20211116214530749

image-20211116214359131

 //二叉树节点个数函数
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:二叉树的后序遍历

题目

image-20211116214847981

image-20211116221210027

//二叉树
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:相同的树

题目

image-20211114214742547

image-20211114233423560

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:对称二叉树

题目

image-20211116072024229

image-20211116073040713

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:另一棵树的子树

题目

image-20211116074903027

image-20211116202318803

 //判断是否是相同的树
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:二叉树遍历

题目

image-20211118001943031