资讯专栏INFORMATION COLUMN

[LeetCode] 226. Invert Binary Tree

xiaodao / 453人阅读

Problem

Invert a binary tree.

Example:

Input:

     4
   /   
  2     7
 /    / 
1   3 6   9
Output:

     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 f*** off.
Solution Recursive
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
Iterative
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Queue queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode left = node.left;
            node.left = node.right;
            node.right = left;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return root;
    }
}

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

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

相关文章

  • Leetcode PHP题解--D59 226. Invert Binary Tree

    摘要:题目链接题目分析反转二叉树。思路类似反转两个变量,先把左右子树存进单独的变量,再相互覆盖左右子树。并对子树进行相同的操作。最终代码若觉得本文章对你有用,欢迎用爱发电资助。 D59 226. Invert Binary Tree 题目链接 226. Invert Binary Tree 题目分析 反转二叉树。 思路 类似反转两个变量,先把左右子树存进单独的变量,再相互覆盖左右子树。 并...

    miqt 评论0 收藏0
  • LeetCode 之 JavaScript 解答第226题 —— 翻转二叉树(Invert Bina

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

    MingjunYang 评论0 收藏0
  • 226. Invert Binary Tree

    摘要:题目链接思路如果需要反转一个二叉树,那么我们需要遍历整个树的所有节点。这两种办法分别可以用迭代或者递归的办法实现。算法复杂度递归时间空间时间空间代码递归 题目链接:Invert Binary Tree 思路:如果需要反转一个二叉树,那么我们需要遍历整个树的所有节点。如果想遍历所有的节点,我们可以用Depth First Search(DFS)或者Breadth First Search...

    cppprimer 评论0 收藏0
  • [Leetcode] Invert Binary Tree 翻转二叉树

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

    leone 评论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 评论0 收藏0

发表评论

0条评论

xiaodao

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<