BM33. [二叉树的镜像]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM33. 二叉树的镜像

https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=295&sfm=github&channel=nowcoder

源二叉树

镜像二叉树

从上到下进行遍历，然后交换左右子节点就可以了？简单dfs即可

图解过程

模板处理

public TreeNode Mirror (TreeNode pRoot) {
        //处理当前节点
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }

如何处理当前节点，就是交换左右子树，直接时候用我们的swap函数即可

       if(pRoot == null)
            return null;
        //可以将其抽象为一个swap操作按照swap的操作就非常的容易理解交换可以想象交换数组的连个树
        TreeNode tmp =  pRoot.right;
        pRoot.right = pRoot.left;
        pRoot.left = tmp;

完整题解

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
       if(pRoot == null)
            return null;
        //可以将其抽象为一个swap操作按照swap的操作就非常的容易理解
        TreeNode tmp =  pRoot.right;
        pRoot.right = pRoot.left;
        pRoot.left = tmp;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

复杂度分析

• 时间复杂度：O(n)，二叉树前序遍历的时间复杂度
• 空间复杂度：O(n)，新建一个二叉树进行返回