[NC]72. 二叉树的镜像

🚩传送门：牛客题目

题目

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

复杂度分析

时间复杂度：，其中 为二叉树节点的数目，时间复杂度同归并排序。我们会遍历二叉树中的
每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。

空间复杂度：，使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情
况下，二叉树的高度与节点个数为对数关系，即 。而在最坏情况下，树形成链状，空间复杂度
为。

官方代码

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}