LeetCode:Invert Binary Tree - 反转二叉树
LeetCode:Invert Binary Tree - 反转二叉树
北风其凉 发表于2年前
LeetCode:Invert Binary Tree - 反转二叉树
  • 发表于 2年前
  • 阅读 479
  • 收藏 5
  • 点赞 1
  • 评论 1

腾讯云 学生专属云服务套餐 10元起购>>>   

摘要: LeetCode第226题,Invert Binary Tree,使用Java语言的解题方案

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

共有 人打赏支持
北风其凉
粉丝 112
博文 486
码字总数 458677
作品 4
评论 (1)
啦啦啦拉拉
第一种超级易名好理解,分析下算法复杂度啊[0]
×
北风其凉
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: