剑指 Offer 27. 二叉树的镜像

剑指 Offer 27. 二叉树的镜像

解题思路：递归

遇到关于链表与二叉树的相关问题时，我们都要考虑递归是否可以解决，因为这两种数据结构本身就带有递归性质。譬如：二叉树的前序，中序，后序遍历都可以使用递归算法完成。

递归算法需要明确两个目标：

1. 返回条件。如果没有设定递归中止条件，就会造成栈溢出
2. 递推算法。我们需要明确如何将一个大问题划分成规模更小的子问题

在本题中：

1. 返回条件：当节点 root 为空时，即返回 null
2. 递推算法：
   图一为原二叉树，图二为二叉树的镜像；不难找出递推关系；输入原二叉树的根节点，对其进行镜像翻转其结果等价于：对根节点的右子树进行镜像翻转，再对根节点的左子树进行镜像翻转，最后让原左子树和原右子树调换位置，使其变成根节点的左子树和右子树。```java TreeNode left = mirrorTree(root.right); TreeNode right = mirrorTree(root.left);

root.left = left; root.right = right;

<a name="06e004ef"></a>
#### 代码
_Java_
```java
/**
 * 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 left = mirrorTree(root.right);
        TreeNode right = mirrorTree(root.left);
        root.left = left;
        root.right = right;
        return root;
    }
}

复杂度分析

• 时间复杂度：O(N)
  N 为二叉树的节点个数，建立二叉树镜像需要遍历二叉树所有的节点，所以时间复杂度为：O(N)
• 空间复杂度：O(N)
  空间复杂度为递归栈的深度，最差的情况即：当一个二叉树退化为链表，此时需要的额外空间为：O(N)