题解 | #二叉树的镜像#

方法一（递归）

1.题意整理

• 给定一颗二叉树。
• 求该二叉树的镜像。

2.思路整理

• 递归结束条件：当前节点为空。
• 递归如何传递：每次需要交换当前节点的左子节点和右子节点，然后依次往左子树方向递归、往右子树方向递归。
• 递归的返回值：每次返回当前节点。

图解展示：

3.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        //递归结束条件
        if(pRoot==null) return pRoot;
        //交换当前节点的左右子节点
        TreeNode tmp=pRoot.left;
        pRoot.left=pRoot.right;
        pRoot.right=tmp;
        //往左子树方向遍历
        Mirror(pRoot.left);
        //往右子树方向遍历
        Mirror(pRoot.right);
        return pRoot;
    }
}

4.复杂度分析

• 时间复杂度：需要遍历树中所有节点，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要深度不超过n的栈，所以空间复杂度为$O(n)O(n)$。