Day28 _序列与顺序_剑指Offer
IT蛋
2023-04-19 21:42
阅读2266
序列化二叉树
Hard 原题连接：序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
解题思路
- 如何序列化二叉树（以什么顺序序列化）
- 先序遍历：根 （左）（右）的顺序，根（根左右）（根左右）,可以确定当前第一个是根节点，遍历左子树，直到叶子节点，之后是右子树
- 中序遍历：（左） 根 （右）的顺序，很难判断出根节点的位置，
- 后序遍历：（左）（右） 根 的顺序，同上不便判断出根节点和左右节点之间的区分
- 二叉树有几种状态需要区别
- 当前节点：直接把值当字符存储，空节点（叶子节点的子节点）使用特殊字符存储 "#"
- 子节点与根：使用字符连接，便于反序列化时区分各个值 “-”
综上，序列化使用先序遍历，判断是否是null，存储当前值，遍历左子树，遍历右子树
反序列化则是按顺序读取序列化的值，凭借自己拆分的字符，拆成一个个数字，按先序连接
Java代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null) return "#";
StringBuilder sb = new StringBuilder();
sb.append(root.val);
sb.append("_");
sb.append(serialize(root.left));
sb.append("_");
sb.append(serialize(root.right));
String str = sb.toString();
return str;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] values = data.split("_");
Queue<String> queue = new LinkedList<>();
for(int i = 0; i < values.length; i++) {
queue.add(values[i]);
}
return reconOrder(queue);
}
//组成树
public static TreeNode reconOrder(Queue<String> queue) {
String value = queue.poll();
if(value.equals("#")){
return null;
}
TreeNode head = new TreeNode(Integer.valueOf(value));
head.left = reconOrder(queue);
head.right = reconOrder(queue);
return head;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
字符串的排列
medium 原题连接：字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例：
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
解题思路
字符的所有排列，理论上，一个长度为n的字符最大排列数应该是 !n 个，但是例子中发现存在重复字符，比如 abb
思路变为每一个字符在每一个位置只能出现一次（每一个位置都设置一个hashset存储已经在这个位置站过的字符）
第一个位置会遍历n次，第二位置会遍历n-1次....最后位会遍历1次，总计 !n 次
但是，一旦出现已经在某个位置重复选过，剪枝
直至拼接长度到达目标长度
Java代码
class Solution {
// 1.用什么存储
char[] sortStr;
List<String> ans = new LinkedList<>();
public String[] permutation(String s) {
// 2.初始化：String 转 charArray
sortStr = s.toCharArray();
dfs(0);
return ans.toArray(new String[ans.size()]);
}
// 3.dfs遍历运算，终止条件是什么，dfs如何递归
public void dfs(int index) {
// 4.剪枝条件
if(index == sortStr.length-1) {
ans.add(String.valueOf(sortStr));
return;
}
HashSet<Character> set = new HashSet<>();
for(int i=index; i<sortStr.length; i++) {
if(set.contains(sortStr[i]))continue;
set.add(sortStr[i]);
swap(i, index);
dfs(index + 1);
swap(i, index);
}
return;
}
// 5.交换函数
public void swap(int a, int b) {
char mid = sortStr[a];
sortStr[a] = sortStr[b];
sortStr[b] = mid;
}
}
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
内容推荐
刷题经验分享
60
Leetcode文章资源分享：高效刷满500题方法论
170
这几天刷题算法，我也是入门基础，虽然还是难，思路啥的，但是温习了很多，比如map集合的containsKey等等 set的去重 map的计数等等今天刷了一道算法中等二维数组的 零矩阵 虽然还是查阅了资料但是没看题解，就是二维数组的列长度计算。。跌跌撞撞终于写出了一道中等题目[流泪][流泪]，，很开心。想放弃的，但是写出来那种成就感很足，继续加油吧[呲牙]
10
才发现力扣评论区也显示ip属地了，是从今天还是昨天开始的，刚注意到[捂脸]
15
学习总结 Python 算法 前端关于过去一年的学习情况去年尝试学习了MCU学了有一周左右弃了，然后抄网上的flask框架的项目，搞到一半发现有一些前端的问题不怎么明白，然后开始刷前端当前学到BOM，然后是算法刷了100多道 目前除了动态规划不怎么行 其他题目看到都还有点思路
8
