二叉树基础oj练习(单值二叉树、相同的树、二叉树的前序遍历)

简介: 二叉树基础oj练习(单值二叉树、相同的树、二叉树的前序遍历)

讲了这么多数据结构相关的知识(可以看我的数据结构文章专栏):

抓紧刷题巩固一下了


1.单值二叉树


965. 单值二叉树 - 力扣(LeetCode)


题目描述


思路1


利用递归:


首先检查根与左右节点的值是否相等,如果不相等就能直接返回false ,都一样就依次进入左右子树开始检查子树。


对于每个节点,它会检查其左子节点和右子节点的值是否与当前节点的值相同,如果不同则返回 false。如果左右子树都满足条件,则继续递归地检查左子树和右子树


递归的终止条件是当遍历到叶子节点时,此时返回 true


代码1


bool isUnivalTree(struct TreeNode* root) {
    if(root==NULL)
    return true;
    if(root->left!=NULL&&root->left->val!=root->val)
    {
        return false;
    }
    if(root->right!=NULL&&root->right->val!=root->val)
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}


思路2


首先检查根节点是否为空,如果为空则直接返回 true


然后,代码会递归地检查左子树和右子树。对于每个节点,它会检查其左子节点和右子节点的值是否与当前节点的值相同,如果不同则返回 false。同时,它也会递归地检查左子树和右子树是否为unival树(一旦不满足条件,直接返回false)


满足了就走到最后,返回true


代码2


bool isUnivalTree(struct TreeNode* root) {
    if(root==NULL)//看根
    {
          return true;
    }
    if(root->left)//左子树不为空就先看左子树符合否
    {
        if(root->left->val!=root->val||!isUnivalTree(root->left))
        return false;
    }
    if(root->right)//右子树不为空
    {
        if(root->right->val!=root->val||!isUnivalTree(root->right))
        return false;
    }
    return true;
}


2.相同的树


100. 相同的树 - 力扣(LeetCode)


题目描述



思路


先根和根比,比完再比左子树和右子树

1. 两者都是空时也相等

2. 左节点或右节点一个存在一个不存在返回false;都存在不相等也是false

3.开始递归,都是NULL时返回true或者返回false停止


代码


bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    if(p==NULL&&q!=NULL)
    {
        return false;
    }
    if(q==NULL&&p!=NULL)
    {
        return false;
    }
    if(p->val!=q->val)
    {
        return false;
    }
   bool left= isSameTree(p->left,q->left);
   bool right= isSameTree(p->right,q->right);
    return left&&right;
}



3.二叉树的前序遍历


144. 二叉树的前序遍历 - 力扣(LeetCode)


代码


int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);
}
void preorder(struct TreeNode* root, int* a, int* i)
{
    if (root == NULL)
    {
        return;
    }
    a[*i] = root->val;
    (*i)++;
    preorder(root->left, a, i);
    preorder(root->right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = TreeSize(root);
    *returnSize=n;
    int* a=(int*)malloc(sizeof(int)*n);
    int i=0;
    preorder(root,a,&i);
    return a;
}


思路


1.首先题目要求放到malloced的数组里,那就要考虑大小的问题,最后还是运用TreeSize来求一下树里元素的数量比较好,求出来后直接赋值给*returnsize


2.一般使用递归,但是我们已经在函数里面动态开辟了,递归每次调用会消耗很多,最好的办法还是在构建一个函数来进行前置遍历和放入的操作。


3.考虑到参数设置问题,root要有,数组a也要有。那想到需要一个下标才能确保递归时正确放到位置,这个下标还不能在递归函数里面定义,那样没用(都是新的,独立的变量)。


所以要作为参数传入的同时还能保证递归时改变的都是同一个变量那就有两种方法:


全局变量

传入地址:地址虽然也是临时拷贝,但是都是指向同一块区域


目录
相关文章
|
11月前
|
存储 Web App开发 JavaScript
你的object可能没别人的快/小
本文深入探讨了JavaScript对象在V8引擎中的内存管理和优化策略,特别是在处理大规模数据时可能出现的性能和内存问题。
388 56
|
监控 JavaScript 前端开发
Web Vitals:提升网页用户体验的关键技术
【7月更文挑战第18天】Web Vitals 为开发者提供了一套全面而具体的性能优化指南,帮助开发者从多个维度提升网页的用户体验。通过关注 LCP、FID 和 CLS 等核心指标,并采取有效的优化策略,我们可以让网页加载更快、交互更流畅、视觉更稳定,从而赢得用户的青睐和信任。在未来的发展中,持续关注并优化 Web Vitals 指标将是提升网页用户体验的重要方向。
|
监控 NoSQL Redis
redis-server --service-install redis.windows.conf --loglevel verbose 命令的作用是什么?
redis-server --service-install redis.windows.conf --loglevel verbose 命令的作用是什么?
629 3
|
Shell Linux
Linux|shell编程|拷贝大文件之显示进度条
Linux|shell编程|拷贝大文件之显示进度条
386 0
|
JavaScript 前端开发
计算属性和监视属性的区别
计算属性和监视属性的区别
132 0
|
存储 数据采集 人工智能
Python编程入门到实践,你的编程之旅从这里开始
Python编程入门到实践,你的编程之旅从这里开始
85 0
|
监控 JavaScript 前端开发
Vue框架设计的核心要素
Vue框架设计的核心要素
125 0
|
C++ Python
LeetCode 1.两数之和【力扣——C/C++/Python三种编程语言题解】
LeetCode 1.两数之和【力扣——C/C++/Python三种编程语言题解】
150 0
|
运维 监控 测试技术
北京云栖黑科技:智能服务让运维工程师以一当十
输入系统相关的型号和参数,一键操作就可以上云?对于系统的各种问题,可以智能诊断并自动修复?遇到大促心里没底,用自动压测工具提前演练?这些听起来有些“过分”的需求,通过北京云栖大会上展出的“智能迁云工具”、“智能顾问”、“自动压测与演练预警”三大工具,即可轻松实现。