BM33. [二叉树的镜像]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM33. 二叉树的镜像
源二叉树
镜像二叉树
从上到下进行遍历，然后交换左右子节点就可以了？简单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)，新建一个二叉树进行返回
