【刷算法】翻转二叉树的递归和非递归解法

简介: 【刷算法】翻转二叉树的递归和非递归解法

题目描述


操作给定的二叉树,将其变翻转为源二叉树的镜像。


输入描述:


image.png

解题思路


递归版本


首先,对数据结构比较了解的话会想到用递归来解决。 所谓递归,在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法(来自维基百科)。这个解释还是比较教条的,对于工程师来说,首先要思考:


  1. 分解问题后的子问题是什么,也就是重复的那一部分是什么?
  2. 什么时候结束重复?即终止条件是什么


回到翻转二叉树的问题,我们梳理一遍整个翻转过程:

  root开始,交换root的left元素和root.right元素
    root.left开始,交换root.left.left元素和root.left.right元素
    root.right开始,交换root.right.left元素和root.right.right元素
    ...
    ...

可以看出来重复的部分是:交换X元素的left和right元素,用伪代码表示为:

 temp = X.left;
    X.left = X.right;
    X.right = temp;

那么终止条件是什么呢?很显然是当元素为null时,它就谈不上去交换左右子元素了,所以X=null时终止递归。 此时代码就很好写了:

function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } 
    function Mirror(root){
        // 终止条件
        if(root === null)
            return;
        // 重复操作的部分
        var temp = root.left;
        root.left = root.right;
        root.right = temp;
        //分别再对左右子节点进行同样的操作
        Mirror(root.left);
        Mirror(root.right);
    }


非递归版本


非递归版本可以从树的层次遍历上找到灵感,无非就是按照层来遍历树的节点,且一边遍历一边交换当前节点的左右子节点,直到遍历完毕就OK

  function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } 
    function Mirror(root){
        if(root === null)
            return;
        var queue = [];// 队列来辅助遍历树
        queue.push(root);
        while(queue.length !== 0) {
            var cur = queue.shift();// 弹出队列头的元素,交换它的左右子节点
            if(cur !== null) {
                var temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;
                queue.push(cur.left)// 左子节点入队
                queue.push(cur.right);// 右子节点入队
            }  
        }    
    }
相关文章
|
20天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
24天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
47 5
|
23天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
38 2
|
26天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
28 0
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
24 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
28 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
28 0
|
2月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
2天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
3天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。