跃迁引擎

空気を読んだ雨降らないでよ

iOS Research & Development


镜像的二叉树

剑指 Offer 27. 二叉树的镜像

题目

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

例如输入:

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

镜像输出:

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

示例 1:

1
2
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

限制:

1
0 <= 节点个数 <= 1000

题解

所谓镜像就是与原物互成映射,原物的左是镜像的右,原物的右是镜像的左。而在二叉树当中,就是各左右节点互成镜像,思路很简单,递归这棵树,然后交换其各子树的左右节点即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 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 null;
}
// 左右子树交换
mirrorTree(root.left);
mirrorTree(root.right);
// 左右子树节点交换
// 保存交换前的子树左节点,用于与子树右节点进行交换
TreeNode tmpLeft = root.left;
// 左 <-> 右
root.left = root.right;
// 右 <-> 左
root.right = tmpLeft;

return root;
}
}
最近的文章

二叉树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先 …

, , 开始阅读
更早的文章

对称的二叉树

剑指 Offer 28. 对称的二叉树 …

, , 开始阅读
comments powered by Disqus