LeetCode题解—二叉树的镜像
前言
五一快乐老铁们，祝大家假期愉快～
然后说个事，以后可能会减少算法题的文章了，因为我对于算法也没有很深的理解，只是和大家分享一下我刷题的过程，所以可能对大家的帮助不大。
一周两更Android系列肯定不会变，然后剩下的一篇我会慢慢尝试新的内容形式，再想想看吧。
今天的算法题目是 二叉树的镜像。
题目
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
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]
限制：0 <= 节点个数 <= 1000
解法一
登登，其实这道题的精髓就在于每个子树的左右节点都进行了替换，就完成了一个镜像。所以我们可以通过递归的方式，交换每个左右子节点。
当节点为null，返回null，否则就返回传进来的节点。
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
//继续处理下面的节点
TreeNode leftRoot = mirrorTree(root.right);
TreeNode rightRoot = mirrorTree(root.left);
//交换左右节点
root.left = leftRoot;
root.right = rightRoot;
return root;
}
}
复杂度
时间复杂度：O(n) 空间复杂度：O(n)。（递归使用栈空间）
解法二
利用集合来遍历树的每个节点，然后将每个节点的左右节点交换，一直到所有节点都完成即可。
这里用栈的方式进行处理：
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
//根节点入栈
Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
//遍历每个节点
while(!stack.isEmpty()) {
//出栈一个节点
TreeNode node = stack.pop();
//添加左右子节点
if(node.left != null) stack.add(node.left);
if(node.right != null) stack.add(node.right);
//交换左右节点
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
return root;
}
复杂度
时间复杂度：O(n) 空间复杂度：O(n)
参考
https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-04-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录