剑指 Offer 27. 二叉树的镜像【递归、迭代】

题目描述

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

例如输入:

4

/ \

2 7

/ \ / \

1 3 6 9
镜像输出:

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
2
3
4
5
6
7
8
9
10
11
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
// 先记录下root的左右孩子结点,再进行递归调用
TreeNode left = root.left;
TreeNode right = root.right;
root.left = mirrorTree(right);
root.right = mirrorTree(left);
return root;
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(n)

方法二:迭代

将未交换的结点存入栈中,将交换的结点的孩子节点存入栈,使得每个结点都交换左右孩子结点即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public TreeNode mirrorTree2(TreeNode root) {
if (root == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
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 temp = node.left;
node.left = node.right;
node.right = temp;
}
return root;
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(n)

资源

  1. https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
  2. 《剑指offer》

剑指 Offer 27. 二叉树的镜像【递归、迭代】

http://example.com/2021/04/19/27-二叉树的镜像/

Author

John Doe

Posted on

2021-04-19

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.