【LeetCode】二叉树的镜像 Java 题解

关注

发布于: 1 小时前

题目描述

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：
     4   /   \  2     7 / \   / \1   3 6   9镜像输出：
     4   /   \  7     2 / \   / \9   6 3   1
 
示例 1：
输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
在数据结构考察中，最基本的考察方式是树的遍历，包含前/中/后/层序遍历。这种遍历题目，大家接触的比较多，解决题目一般比较顺利。
还有一种需要建立树结构返回，这种题目相对较少，多加练习就能掌握好。
解决树问题常见的思想是递归。程序调用自身的编程技巧称为递归（recursion）。
使用递归思想解决问题的时候，需要注意以下两点。1. 注意递归的终止条件，防止无限递归。2.将当前层处理的问题最小化，明确问题。
根据上述知识的铺垫，结合题目，镜像可以简单理解为左右子树调换位置。代码如下：

代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode mirrorTree(TreeNode root) {        if (root == null) {            return root;        }
        return buildTree(root);    }
    public TreeNode buildTree(TreeNode node) {        if (node == null) {            return null;        }
        TreeNode newNode = new TreeNode(node.val);        newNode.left = buildTree(node.right);        newNode.right = buildTree(node.left);
        return newNode;    }}

复制代码

总结

上述算法时间复杂度是 O(n), 空间复杂度是 O(n)
坚持每日一题，加油！

发布于: 1 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/ea5b0b2ab5702dc25a9f44a61】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】二叉树的镜像 Java 题解

题目描述

思路分析

代码

总结

HQ数字卡

评论