- 二叉树的序列化与反序列化
- DFS
- BFS
- 验证二叉树的前序序列化是否合法
- 子结构
- 同一个树中找相同的子树
- t是否为s的子结构
- t是否为s的子树
- 链表是否在二叉树中被完全覆盖
添加链接描述
注意题目中的这句话：
不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。所以反序列化时用队列而不是数组或列表，因为数组或列表需要一个全局的索引下标。
选择前序遍历，是因为 根|左|右的打印顺序，在反序列化时更容易定位出根节点的值。
遇到 null 节点也要翻译成特定符号，反序列化时才知道这里是 null。
public class Codec {
public String serialize(TreeNode root) {
if(root==null){
return "X,"; //注意这里有个,
}
String left=serialize(root.left);
String right=serialize(root.right);
return root.val+","+left+right; //根左右先序，反序列化也要保持一致。
}
public TreeNode deserialize(String data) { //data就是serialize函数的返回
Dequeq=new ArrayDeque<>(Arrays.asList(data.split(",")));
return buildTree(q);
}
private TreeNode buildTree(Deque q) {
// if(q.isEmpty()){//q无需判空，q为空时递归恰好结束！
// return null;
// }
String s = q.removeFirst();
if(s.equals("X")){ //不要== 不要== 不要== 不要==
return null;
}
//根左右
TreeNode node = new TreeNode(Integer.parseInt(s));
node.left=buildTree(q);
node.right=buildTree(q);
return node;
}
}
BFS
了解
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
Queue queue = new linkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append("X,");
} else {
sb.append(node.val + ",");
queue.offer(node.left);
queue.offer(node.right);
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == "") {
return null;
}
Queue strQ = new ArrayDeque<>(Arrays.asList(data.split(",")));
TreeNode root = new TreeNode(Integer.parseInt(strQ.poll()));
Queue nodeQueue = new ArrayDeque<>();
nodeQueue.offer(root);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.poll();
String left = strQ.poll();
String right = strQ.poll();
if (!left.equals("X")) {
node.left = new TreeNode(Integer.parseInt(left));
nodeQueue.add(node.left);
}
if (!right.equals("X")) {
node.right = new TreeNode(Integer.parseInt(right));
nodeQueue.add(node.right);
}
}
return root;
}
}
验证二叉树的前序序列化是否合法
添加链接描述
利用重建二叉树的思想来验证是否合法，如果能重建成功则合法，如果重建失败则非法。
class Solution {
public boolean isValidSerialization(String preorder) {
Dequequeue=new ArrayDeque<>(Arrays.asList(preorder.split(",")));
if(build(queue)){
return queue.isEmpty();
}
return false;
}
private boolean build(Deque queue) {
if(queue.isEmpty()){
return false;
}
String poll = queue.poll();
if(poll.equals("#")){
return true;
}
//左子树 && 右子树
return build(queue) && build(queue);
}
}
子结构
同一个树中找相同的子树
652. 寻找重复的子树
本题相同的是子树
思路：
解决此题的关键是以下两点：
1、以我为根的这棵二叉树长啥样？
2、以其他节点为根的二叉树都长啥样？
我得知道自己长啥样，还得知道别人长啥样，然后才能知道有没有人跟我重复
长啥样怎么体现呢？——序列化成字符串
class Solution {
Map map=new HashMap();
Listans=new ArrayList<>();
public List findDuplicateSubtrees(TreeNode root) {
if(root==null){
return ans;
}
dfs(root);
return ans;
}
private String dfs(TreeNode root) {
if(root==null){
return "+";
}
String left=dfs(root.left);
String right=dfs(root.right);
String temp=root.val+","+left+","+right;
if(map.getOrDefault(temp,0)==1){
ans.add(root);
}
map.put(temp,map.getOrDefault(temp,0)+1);
return temp;
}
}
t是否为s的子结构
添加链接描述
本题相同的是子结构，不需要子树！所以不能用序列化。
正确思路：
class Solution {
public boolean isSubStructure(TreeNode a, TreeNode b) {
if(a==null && b==null){
return true;
}
if(a==null || b==null){
return false;
}
return isSame(a,b) || isSubStructure(a.left,b)||isSubStructure(a.right,b);
}
private boolean isSame(TreeNode a, TreeNode b) {
//注意这里并不是 a==null&&b==null 因为只需要子结构相同而不是子树相同
if(b==null){
//b为null时a是否为null都可以
return true;
}
if(a==null){
//此时b不为null，但a为null说明不符合
return false;
}
if(a.val!=b.val){
//都不为null，但是值不同当然
return false;
}
return isSame(a.left,b.left) && isSame(a.right,b.right);
}
}
t是否为s的子树
上题只需是其子结构即可，本题必须是子树。
添加链接描述
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(subRoot==null){
return true;
}
if(root==null){
return false;
}
return isSame(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
private boolean isSame(TreeNode a, TreeNode b) {
//子树则就是下面的判断形式了
if(a==null && b==null){
return true;
}
if(a==null || b==null){
return false;
}
if(a.val!=b.val){
return false;
}
return isSame(a.left,b.left) && isSame(a.right,b.right);
}
}
链表是否在二叉树中被完全覆盖
添加链接描述
和上题很像
区别在于isSub中判断二者是否相同时不一样，上题是必须一模一样的子结构，本体是树中能覆盖链表即可。
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
if (head == null) {
return true;
}
if (root == null) {
return false;
}
//先判断当前的节点，如果不对，再看左子树和右子树呗
return isSub(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
}
private boolean isSub(ListNode head, TreeNode node) {
//特判：链表走完了，返回true
if (head == null) {
return true;
}
//特判：链表没走完，树走完了，这肯定不行，返回false
if (node == null) {
return false;
}
//如果值不同，必定不是啊
if (head.val != node.val) {
return false;
}
//如果值相同，继续看，左边和右边有一个满足即可
return isSub(head.next, node.left) || isSub(head.next, node.right);
}
}
