【每日挠头算法题(7)】对称的二叉树|二叉树的所有路径

简介: 【每日挠头算法题(7)】对称的二叉树|二叉树的所有路径

前言

提示:这里可以添加本文要记录的大概内容:

例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。


提示:以下是本篇文章正文内容,下面案例可供参考

一、对称的二叉树

点我直达~

思路:递归法

  • 1.题目的意思就是判断这棵树是否是轴对称的,所以我们需要将这棵树分成左子树和右子树两部分。
  • 2.给一个left,right指针分别指向左子树和右子树的根。随后判断这两棵树是否是轴对称。
  • 轴对称要点:
  • (1)左右子树的val值是否相等。
  • (2)左子树的左子节点和右子树的右子节点的val值是否相等。
  • (3)左子树的右子节点和右子树的左子节点的val值是否相等。
  • 所以第二第三点递归判断即可。
  • 注意:递归结束的条件是如果其中一个节点为空,或者都为空,返回。

具体代码如下:

//思路:判断左右子树是否对称,
class Solution {
public:
    bool isSameTree(TreeNode* left,TreeNode* right)
    {
        //情况1:其中一个节点为空,返回false;或者两个都为空,返回true
        if(left == nullptr || right == nullptr)
            return left == right;
        //都不为空,先判断左右节点val值是否相等,再递归左右子树
        return left->val == right->val && isSameTree(left->left,right->right) && isSameTree(left->right,right->left);        
    }
    bool isSymmetric(TreeNode* root) 
    {
        if(root == nullptr)
            return true;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        return isSameTree(left,right);
    }
};

时间复杂度:O(n),最坏空间复杂度O(n),当二叉树退化为链式结构时;最好空间复杂度O(logN),当二叉树为满二叉树时

二、二叉树的所有路径

点我直达~

思路:递归法

  • 给一个顺序表path存储二叉树的所有路径,给一个字符串string road代表每一条路,当该条路到达路的尽头,也就是遇到叶子节点时,将road存储到path中。
  • 具体如下:
  • (1)从根节点开始遍历整棵树,如果该节点为空,则不用做什么,返回即可。
  • (2)如果该节点的左右子节点均为空,表明获得了一条路径,将该路径road存储到path中,再返回即可。
  • (3)如果不是以上两种情况,则继续往下遍历即可,可以先遍历左子树,再遍历右子树,或者相反均可。
    - 注意:每次调用栈桢,road在每一层栈桢中都是不相同的,而一旦更新path,在其他每层栈桢中都会同时更新。

图解如下:

具体代码如下:

class Solution {
public:
    void PrevOrder(TreeNode* root,string road, vector<string>& path)
    {
        //只要该节点不为空,则可继续走
        if(root!=nullptr)
        {
            road+=to_string(root->val);
            //只要左右节点都为空,表明获得一条路径
            if(root->left == nullptr && root->right == nullptr)
            {
                path.push_back(road);
            }
            //如果不是以上的情况,则可以继续递归
            else
            {
                node+="->";
                PrevOrder(root->left,road,path);
                PrevOrder(root->right,road,path);
            }
        }
        return ;
    }
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        string node = "";
        vector<string> path;
        PrevOrder(root,road,path);
        return path;
    }
};

时间复杂度O(n^2),每次递归需要对road进行拷贝构造,时间代价为O(n),递归n个节点,为O(n^2);空间复杂度O(n^2),每次调用栈桢进行road的拷贝,消耗N^2的空间;

总结

通过这次算法,我深知自己的递归理解得不够透彻,所以需要继续练习递归二叉树方面的题型,说实话,理解递归还是比较重要的。

相关文章
|
9天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
31 2
|
23天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
50 5
|
2月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
2月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
74 5
|
2月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
73 0
|
1天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
1天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
|
11天前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
12天前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
|
12天前
|
算法
基于龙格库塔算法的锅炉单相受热管建模与matlab数值仿真
本设计基于龙格库塔算法对锅炉单相受热管进行建模与MATLAB数值仿真,简化为喷水减温器和末级过热器组合,考虑均匀传热及静态烟气处理。使用MATLAB2022A版本运行,展示自编与内置四阶龙格库塔法的精度对比及误差分析。模型涉及热传递和流体动力学原理,适用于优化锅炉效率。

热门文章

最新文章