文档章节

LeetCode:Invert Binary Tree - 反转二叉树

北风其凉
 北风其凉
发布于 2016/02/11 23:03
字数 311
阅读 568
收藏 5

1、题目名称

Invert Binary Tree(反转二叉树)

2、题目地址

https://leetcode.com/problems/invert-binary-tree/

3、题目内容

英文:

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

中文:反转一颗二叉树。

4、解题方法1

本题有两种解题方法,第一种是通过递归的方式解决问题,代码行数少,可读性强。

Java代码如下:

/**
 * LeetCode 226 - Invert Binary Tree
 * @文件名称 Solution.java
 * @文件作者 Tsybius2014
 * @创建时间 2016年2月11日 下午10:34:59
 */
public class Solution {
    /**
     * 翻转二叉树
     * @param root 二叉树的根
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

5、解题方法2

使用迭代方式解决本问题的Java代码如下:

import java.util.Stack;

/**
 * LeetCode 226 - Invert Binary Tree
 * @文件名称 Solution.java
 * @文件作者 Tsybius2014
 * @创建时间 2016年2月11日 下午10:34:59
 */
public class Solution {
    /**
     * 翻转二叉树
     * @param root 二叉树的根
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            stack.pop();
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return root;
    }
}

END

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 115
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
加载中

评论(1)

啦啦啦拉拉
啦啦啦拉拉
第一种超级易名好理解,分析下算法复杂度啊[0]
PAT A1102. Invert a Binary Tree (25)

Invert a Binary Tree (25) https://www.patest.cn/contests/pat-a-practise/1102 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue The followin......

阿豪boy
2017/03/11
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
反转二叉树

原题   Invert a binary tree.   to 题目大意   将一棵二叉树进行翻转。 解题思路   对每一个结点,将它的左右子树进行交换,再对它的左右子结点进行同样的操作。 代码实现 树结点类...

一贱书生
2016/12/28
14
0
LeetCode算法题-Invert Binary Tree

这是悦乐书的第194次更新,第199篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第55题(顺位题号是226)。反转二叉树。例如: 输入: 输出: 本次解题使用的开发工具是eclip...

小川94
12/07
0
0
nomasp 博客导读:Lisp/Emacs、Algorithm、Android

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/44966625 Profile Introduction to Blog 您能看到这篇博客导读...

nomasp
2015/09/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java程序员可知为何公司宁花25K重新招人,也不花20K留住老员工?

身在职场,经常会暗自打听同事工资,尤其是得知身边新入职同事的工资居然比自己高,还高出一大截时,心里自然很不平衡,一心想要离职。 那么,为什么公司宁愿花高价招聘新员工也不愿意给老员...

Java填坑路
7分钟前
2
0
如何通俗地解释什么是网桥?

吴伟祥
11分钟前
1
0
阿里云文件存储(NAS)助力业务系统承载双十一尖峰流量

2018天猫双11全球狂欢节,全天成交额再次刷新纪录达到2135亿元,其中总成交额在开场后仅仅用了2分05秒即突破100亿元,峰值的交易量达到惊人的高度,背后离不开阿里云大数据计算和存储能力的支...

阿里云云栖社区
11分钟前
0
0
【windows 找不到“\\192.168.X.X”,请检查拼写是否正确】错误&139端口和445端口区别

今天像往常一样,通过共享盘访问其他主机时,却出现如题的错误,百思不得其解,毕竟没有改动什么配置啊,地址也没输错啊。 然后就在网上看到了一篇博客,才想起来上周末因为考虑到安全问题,...

fang_faye
12分钟前
0
0
示例Express中路由规则及获取请求参数

本次给大家分享一篇基于express中路由规则及获取请求参数的方法,写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 express中常见的...

前端攻城小牛
15分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部