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

wangbjun 发布于2019-08-22 18:06 / 1165人阅读

摘要：题目描述操作给定的二叉树，将其变翻转为源二叉树的镜像。输入描述解题思路递归版本首先，对数据结构比较了解的话会想到用递归来解决。所谓递归，在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法来自维基百科。

题目描述

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

输入描述:

        1                    1
       /                   / 
      2   3    ——————>     3   2
     /  /               /  / 
    4  5 6  7            7  6 5  4

解题思路

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

分解问题后的子问题是什么，也就是重复的那一部分是什么？

什么时候结束重复？即终止条件是什么

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

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);// 右子节点入队
        }  
    }    
}

私有云混合云非递归二叉树遍历二叉树的遍历二叉树的存储二叉树的存储结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95508.html

【刷算法】求二叉树深度的递归以及非递归解法

摘要：题目描述输入一棵二叉树，求该树的深度。递归解法非递归解法原来标识当前层是否遍历完毕当前弹出元素为时，说明一层以及遍历完毕了，所以最后一层的弹出时不能再往队列里面加了题目描述输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。递归解法 function TreeNode(x) { this.val = x;...

Carl 2019-08-22 18:13 评论0 收藏0
【刷算法】判断二叉搜索树的后序遍历序列的递归实现和非递归实现

摘要：题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。那么对于二叉搜索树的后序遍历的序列来说，最后一个元素即是它的根节点，序列的前某部分元素全部小于最后一个元素，序列的后某部分元素全大于最后一个元素。题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。分析所谓二叉搜索...

Anshiii 2019-08-22 18:20 评论0 收藏0
前端也需要好好的精进自己的算法

摘要：算法前端发展的再快，也不要忘记精进自己的算法，算法是灵魂和核心。我会把我刷过的算法题总结归类，不断完善。算法前端发展的再快，也不要忘记精进自己的算法，算法是灵魂和核心。我会把我刷过的算法题总结归类，不断完善。欢迎大家关注。数组和堆栈数组去重旋转数组如何快速找出两个数之和等于某一个值的两个数？快排排序算法大总结快速找到数组中的最大值多维数组的展开二分查找有效的括...

hersion 2019-08-23 10:36 评论0 收藏0
LeetCode 156 Binary Tree Upside Down 上下翻转二叉树

摘要：翻转以后如下解题思路翻转的形式一开始不是很清楚，但是里面的高票答案给了一个很好的解释。看例子，树的左边最深的底层是，是新的。对于每个，将链接右孩子的指针去掉，将变为当前左孩子的，成为左孩子的。递归的写法递归调用得到新的，并且沿途改变结构。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...

Loong_T 2019-08-16 13:28 评论0 收藏0