LeetCode Invert Binary Tree题目分析

Invert a binary tree. 4 / \ 2 7 / \ / \1 3 6 9 to4 / \ 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.

Subscribe to see which companies asked this question.

题目

翻转一棵二叉树

分析

Approach #1 (Recursive) [Accepted]

递归交换左右子树即可

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    root.left = right;
    root.right = left;
    return root;
}

Approach #2 (Iterative) [Accepted]

利用一个队列即可,就像是层次遍历,不过在里面多加入一个交换的操作

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        TreeNode temp = current.left;
        current.left = current.right;
        current.right = temp;
        if (current.left != null) queue.add(current.left);
        if (current.right != null) queue.add(current.right);
    }
    return root;
}

Paste_Image.png

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 113 Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's su...

21050
来自专栏desperate633

LintCode 在二叉查找树中插入节点题目分析

给定一棵二叉查找树和一个新的树节点,将节点插入到树中。 你需要保证该树仍然是一棵二叉查找树。

8410
来自专栏计算机视觉与深度学习基础

Leetcode 230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth small...

241100
来自专栏计算机视觉与深度学习基础

Leetcode 173 Binary Search Tree Iterator

mplement an iterator over a binary search tree (BST). Your iterator will be ini...

22660
来自专栏desperate633

LintCode 克隆二叉树题目分析代码

10220
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

18050
来自专栏desperate633

LintCode 子树题目分析代码

有两个不同大小的二进制树: T1有上百万的节点; T2有好几百的节点。请设计一种算法,判定 T2是否为 T1的子树。

9020
来自专栏小狼的世界

Aptana的破解

最近写JS比较多,常常苦恼与没有一个顺手的IDE。Editplus虽然用的熟,不过那个的效率太低而且代码看起来也很不方便,经过一个多月的试用,发现了一款好用的编...

12120
来自专栏desperate633

LintCode 把排序数组转换为高度最小的二叉搜索树题目分析代码

显然这个问题可以用递归解决。 中间的节点总是在根节点,所以我们不停的找到中间节点即可,然后分别递归处理左子树和右子树即可

15330
来自专栏轮子工厂

二叉树的四种遍历算法实现

11330

扫码关注云+社区

领取腾讯云代金券