二叉树的镜像

发表于 | 分类于 |
字数统计: 632 字 | 阅读时长 ≈ 2 分钟

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

例如输入：

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

镜像输出：

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

示例:
输入：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
12
13
14
/**
 * 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) {

  }
}

方法一：递归

递归的两个条件如下：

  • 终止条件：当前节点为 null 时返回
  • 交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
  public TreeNode mirrorTree(TreeNode root) {
    if(root == null) return null;

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    mirrorTree(root.left);
    mirrorTree(root.right);
    return root;
  }
}

复杂度分析：

  • 时间复杂度 O(N)： 其中 N 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间
  • 空间复杂度 O(N)： 最差情况下（当二叉树退化为链表），递归时系统需使用 O(N) 大小的栈空间

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：37.5 MB, 在所有 Java 提交中击败了12.77%的用户

方法二：遍历

将根节点放入到队列中，然后不断的迭代队列中的元素。对当前元素调换其左右子树的位置，然后：

  • 判断其左子树是否为空，不为空就放入队列中
  • 判断其右子树是否为空，不为空就放入队列中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
  public TreeNode mirrorTree(TreeNode root) {
    if(root == null) return null;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
      TreeNode node = queue.poll();
      TreeNode temp = node.left;
      node.left = node.right;
      node.right = temp;
      if(node.left != null) queue.offer(node.left);
      if(node.right != null) queue.offer(node.right);
    }
    return root;
  }
}

复杂度分析：

  • 时间复杂度 O(N) ： 其中 N 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间
  • 空间复杂度 O(N)： 最差情况下（当为满二叉树时），队列最多同时存储 N/2 个节点，占用 O(N) 额外空间

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：37.1 MB, 在所有 Java 提交中击败了68.27%的用户