【剑指offer】33.二叉树镜像
【剑指offer】33.二叉树镜像
Leetcode名企之路
发布于 2018-12-26 11:12:25
发布于 2018-12-26 11:12:25
题目
操作给定的二叉树，将其变换为源二叉树的镜像。 二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5题解
首先先理解题意,镜像通过以下几个步骤可以实现：
可以看到首先对根节点的左右进行翻转。 再递归的对左子树，以及右子树进行翻转。 之前讲过，链表的题目分为四个步骤：连过来、指针走、断后路、调状态。 二涉及到树的题目，基本都是递归。 一旦涉及到递归，就要搞清楚两个东西：
- 递归的过程。在这里就是，先翻转根节点，再翻转左子树，再翻转右子树。
- 递归结束的条件。 这里就是当树为Null的时候不翻转。
public class Solution {
public void Mirror(TreeNode root) {
// 递归结束条件
if (root == null) return;
// 交换左右
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 递归
Mirror(root.left);
Mirror(root.right);
}
}同时一般，我们会有一些边界case去检查一下代码的鲁棒性。 比如左右有一个是null
8
/ \
10 Null
/ \
null null 代码执行到交换没啥问题：
8
/ \
Null 10
/ \
null null执行到递归，左子树就结束掉了。 右子树的话还要递归的执行左右子树，也可以执行正确，但是其实没必要。
public class Solution {
public void Mirror(TreeNode root) {
// 递归结束条件
if (root == null) return;
if (roo.left == null && root.left == null) return;
// 交换左右
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 递归
Mirror(root.left);
Mirror(root.right);
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-12-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录