[Leetcode] Invert Binary Tree 翻转二叉树

leone 发布于2019-08-14 16:11 / 954人阅读

摘要：原题链接递归法复杂度时间空间递归栈空间思路这个难倒大神的题也是非常经典的一道测试对二叉树遍历理解的题。递归的终止条件是当遇到空节点或叶子节点时，不再交换，直接返回该节点。代码给出的是后序遍历的自下而上的交换，先序遍历的话就是自上而下的交换。

Invert Binary Tree

Invert a binary tree.

     4
   /   
  2     7
 /    / 
1   3 6   9

     4
   /   
  7     2
 /    / 
9   6 3   1

Trivia: This problem was inspired by this original tweet by Max
Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

原题链接

递归法 复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

这个难倒Max Howell大神的题也是非常经典的一道测试对二叉树遍历理解的题。递归的终止条件是当遇到空节点或叶子节点时，不再交换，直接返回该节点。对于其他的节点，我们分别交换它的左子树和右子树，然后将交换过后的左子树赋给右节点，右子树赋给左节点。代码给出的是后序遍历的自下而上的交换，先序遍历的话就是自上而下的交换。

代码

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return root;
        TreeNode newLeft = invertTree(root.right);
        TreeNode newRight = invertTree(root.left);
        root.left = newLeft;
        root.right = newRight;
        return root;
    }
}

迭代法 复杂度

时间 O(N) 空间 O(1)

思路

迭代法的思路是BFS或者DFS，这两种方法都可以实现，实际上也是二叉树的遍历。BFS用Queue实现，DFS的话将代码中的Queue换成Stack。

代码

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        Queue q = new LinkedList();
        if(root!=null) q.offer(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            TreeNode tmp = curr.right;
            curr.right = curr.left;
            curr.left = tmp;
            if(curr.left!=null) q.offer(curr.left);
            if(curr.right!=null) q.offer(curr.right);
        }
        return root;
    }
}

GPU云服务器云服务器 binary-tree binary-search-tree 二叉树 python二叉树

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

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

LeetCode 之 JavaScript 解答第226题 —— 翻转二叉树（Invert Bina

摘要：算法思路判断树是否为空同时也是终止条件。分别对左右子树进行递归。代码实现判断当前树是否为左右子树结点交换分别对左右子树进行递归返回树的根节点欢迎一起加入到开源仓库，可以向提交您其他语言的代码。 Time：2019/4/21Title: Invert Binary TreeDifficulty: EasyAuthor: 小鹿题目：Invert Binary Tree（反转二叉树） ...

MingjunYang 2019-08-23 17:07 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论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