Question

面试题 27. 二叉树的镜像

题目描述

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

例如输入：

     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

注意：本题与主站 226 题相同：https://leetcode.cn/problems/invert-binary-tree/

解法

方法一：递归

我们先判断根节点是否为空，如果为空，直接返回空。如果不为空，我们交换根节点的左右子树，然后递归地交换左子树和右子树。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点个数。最坏情况下，二叉树退化为链表，递归深度为 $n$，因此系统使用 $O(n)$ 大小的栈空间。

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, x):
#     self.val = x
#     self.left = None
#     self.right = None


class Solution:
  def mirrorTree(self, root: TreeNode) -> TreeNode:
    if root is None:
      return None
    root.left, root.right = root.right, root.left
    self.mirrorTree(root.left)
    self.mirrorTree(root.right)
    return root

/**
 * 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;
    }
    TreeNode t = root.left;
    root.left = root.right;
    root.right = t;
    mirrorTree(root.left);
    mirrorTree(root.right);
    return root;
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  TreeNode* mirrorTree(TreeNode* root) {
    if (!root) {
      return root;
    }
    swap(root->left, root->right);
    mirrorTree(root->left);
    mirrorTree(root->right);
    return root;
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func mirrorTree(root *TreeNode) *TreeNode {
  if root == nil {
    return root
  }
  root.Left, root.Right = root.Right, root.Left
  mirrorTree(root.Left)
  mirrorTree(root.Right)
  return root
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 *   }
 * }
 */

function mirrorTree(root: TreeNode | null): TreeNode | null {
  if (root == null) {
    return root;
  }
  const { left, right } = root;
  root.left = right;
  root.right = left;
  mirrorTree(left);
  mirrorTree(right);
  return root;
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//   TreeNode {
//     val,
//     left: None,
//     right: None
//   }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  fn dfs(root: &mut Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
      let mut node = node.borrow_mut();
      let temp = node.left.take();
      node.left = node.right.take();
      node.right = temp;
      Self::dfs(&mut node.left);
      Self::dfs(&mut node.right);
    }
  }

  pub fn mirror_tree(mut root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    Self::dfs(&mut root);
    root
  }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *   this.val = val;
 *   this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function (root) {
  if (!root) {
    return null;
  }
  const { left, right } = root;
  root.left = right;
  root.right = left;
  mirrorTree(left);
  mirrorTree(right);
  return root;
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   public int val;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
  public TreeNode MirrorTree(TreeNode root) {
    if (root == null) {
      return root;
    }
    TreeNode t = root.left;
    root.left = root.right;
    root.right = t;
    MirrorTree(root.left);
    MirrorTree(root.right);
    return root;
  }
}

方法二

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, x):
#     self.val = x
#     self.left = None
#     self.right = None


class Solution:
  def mirrorTree(self, root: TreeNode) -> TreeNode:
    if root is None:
      return root
    left = self.mirrorTree(root.left)
    right = self.mirrorTree(root.right)
    root.left = right
    root.right = left
    return root