27.二叉树的镜像
面试题27. 二叉树的镜像
难度简单15
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4 / 2 7 / / 1 3 6 9
镜像输出：
4 / 7 2 / / 9 6 3 1
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
1.递归
时间复杂度:O(n) 建立二叉树的所有结点遍历一遍
空间复杂度:O(n) 最坏情况下 二叉树退化成链表，需要n个存储空间。
//1.暂存左节点
//2.递归遍历右节点。
// a.右节点不为空继续下一层
// b.右节点为空 直接作为根节点的左节点。
//3.递归遍历左节点
// a.左节点不为空继续下一层
// b.右节点为空 直接作为根节点的右节点。
// 如此反复就可以修改。
public TreeNode mirrorTree(TreeNode root) {
//递归
if(root == null ) return null;
TreeNode temp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(temp);
return root;
}
2.使用栈
时间复杂度:O(n) 遍历一下结点的个数
空间复杂度:O(n) 存储所有结点的次数
//1.根节点存储到stack中
//2.当stack 不为null 将根节点pop出来。
// a.如果root.left不为null stack.push -> root.left
// b.如果root.right不为null stack.push -> root.right
//3.暂存left节点
// a.交换左右节点 依次循环遍历。
//返回根节点
public TreeNode mirrorTree(TreeNode root) {
if(root == null){
return null;
}
Stack<TreeNode> stack = new Stack();
stack.push(root);
while(!stack.isEmpty()){
TreeNode root2 = stack.pop();
if(root2.left != null) stack.push(root2.left);
if(root2.right != null) stack.push(root2.right);
TreeNode tmp = root2.left;
root2.left = root2.right;
root2.right = tmp;
}
return root;
}