【剑指offer】27. 二叉树的镜像
2024-09-27 07:56:26
剑指 Offer 27. 二叉树的镜像
知识点：二叉树；递归；栈
题目描述
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
示例
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
解法一：递归法
函数功能：二叉树镜像；
1、终止条件：root==null的时候，返回null；
2、每个节点该做什么：将两个孩子节点互换；
3、什么时候做：递去的时候或者回来的时候都行（前序或者后序都行）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
mirrorTree(root.left);
mirrorTree(root.right);
return root;
}
}
时间复杂度；0(N),每个节点恰好被遍历一次；
空间复杂度；O(N),递归过程中栈的开销；
解法二：栈
自己构造一个辅助栈，依次遍历所有的节点，并交换每个节点的左右孩子；
规则：
压入根节点；
1.弹出；
2.压入弹出节点的左右孩子，并交换；
其实是一层一层，一个节点一个节点的处理。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode top = stack.pop();
if(top.left != null) stack.push(top.left);
if(top.right != null) stack.push(top.right);
TreeNode temp = top.left;
top.left = top.right;
top.right = temp;
}
return root;
}
}
时间复杂度；0(N),每个节点恰好被遍历一次；
空间复杂度；O(N),递归过程中栈的开销
相关链接
最新文章
- CSS list-style属性控制ul标签样式
- 【练习】oracel获取当前session的id方法
- Mono addin 学习笔记 3
- 主机OS重装的节点加回RAC集群步骤示例（11gR2 RAC）
- jqurey click和blur执行时间冲突
- sql cast()和convert()
- 读取文件txt
- 遍历ArrayList与LinkedList,使用FOR与迭代器的区别
- Could not open a connection to your authentication agent
- js将对象转成字符串-支持微信
- Hibernate 笔记1
- c++多态的案例分析
- 反序列py脚本分享（原创）
- sql sever 2012重装数据库时，出现cannot find one or more components, Please reinstall the application.解决方法
- div居中与div内容居中,不一样
- jenkins2.0以后的版本提供自动部署和远程部署功能？
- ARP欺骗与MITM（中间人攻击）实例
- Linux下grep、tail、wc、awk文件处理命令
- CentOS 6.5使用yum快速搭建LAMP环境
- 前端之css语法3