Java JZ27 二叉树的镜像
文章目录
- Java JZ27 二叉树的镜像
- 一、题目描述
- 二、辅助栈
- 三、递归法
使用辅助栈和递归法解决剑指offer JZ27 二叉树的镜像的问题。
一、题目描述
操作给定的二叉树,将其变换为源二叉树的镜像。
数据范围:二叉树的节点数 0≤n≤1000 , 二叉树每个节点的值 0≤val≤1000。
要求: 空间复杂度 O(n) 。本题也有原地操作,即空间复杂度 O(1) 的解法,时间复杂度 O(n)
比如:源二叉树
示例1
输入:{8,6,10,5,7,9,11}
返回值:{8,10,6,11,9,7,5}
示例2
输入:{}
返回值:{}
二、辅助栈
主要是利用栈遍历树的所有节点 node ,并交换每个 node 的左 / 右子节点。
算法流程:
1、特例处理: 当 pRoot为空时,直接返回 null ;
2、初始化: 栈,本文用栈stack ,并加入根节点 pRoot。
3、循环交换: 当栈 stack 为空时跳出;
3.1、出栈: 记为 node ;
3.2、添加子节点: 将 node 左和右子节点入栈;
3.3、交换: 交换 node 的左 / 右子节点。
4、返回值: 返回根节点 pRoot 。
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror (TreeNode pRoot) {
// 当 pRoot为空时,直接返回 null
if(pRoot == null) return null;
// 构建辅助栈
Stack<TreeNode> stack = new Stack<>();
// 根节点入栈
stack.add(pRoot);
//只要栈不为空,就一直遍历
while(!stack.isEmpty()) {
// 节点出栈
TreeNode node = stack.pop();
// 将节点的左、右子树入栈
if(node.left != null) stack.add(node.left);
if(node.right != null) stack.add(node.right);
// 左、右子树交换,中间用tmp过度
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
return pRoot;
}
}
三、递归法
根据二叉树镜像的定义,考虑递归遍历二叉树,交换每个节点的左 / 右子节点,即可生成二叉树的镜像。
解题步骤:
1、特判:如果pRoot为空,返回空
2、每一层都先交换左右子树
3、递归,把pRoot的左子树放到Mirror函数中
4、递归,把pRoot的右子树放到Mirror函数中
5、返回根节点root
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror (TreeNode pRoot) {
// write code here
//如果树是空的,直接返回空结点
if(pRoot == null){
return pRoot;
}
//如果只有根节点,直接返回根节点
if(pRoot.left==null && pRoot.right == null) return pRoot;
//交换结点
TreeNode temp = pRoot.right;
pRoot.right = pRoot.left;
pRoot.left = temp;
//进入递归
Mirror(pRoot.left);
Mirror(pRoot.right);
return pRoot;
}
}