Leetcode 297/449 Serialize and Deserialize Binary Tree区别

今天做449，发现做法好像跟297一模一样。但感觉应该是需要用到BST的特征才是的。谁可以帮忙解释一下？谢谢！
Leetcode297: Serialize and Deserialize Binary TreeLeetcode 449 Serialize and Deserialize Binary Search Tree

你也是一个不爱寻找答案的人吗?

http://www.1point3acres.com/bbs/thread-433802-1-1.html

肥宅快乐水 发表于 2018-7-28 02:01
你也是一个不爱寻找答案的人吗?

http://www.1point3acres.com/bbs/thread-433802-1-1.html

优秀!很优秀!

不是， 我意思你在lc网站上也没怎么看呐（╬￣皿￣）＝○＃（￣＃）３￣） {:8_247:}

肥宅快乐水 发表于 2018-7-28 06:08
不是， 我意思你在lc网站上也没怎么看呐（╬￣皿￣）＝○＃（￣＃）３￣）

肥宅姐姐真是个热心人



是不是也助长了……
没有，什么都没有助长，助长了刷题风气。

vtiaocao 发表于 2018-7-29 02:38
肥宅姐姐真是个热心人

我男的啊。{:8_247:}

助长了什么。。？{:8_247:}{:8_247:}

老大们，我这是刷题帖，不是灌水帖哟

总结一下吧。
两种实现的时间和空间复杂度都是O(N), 所以考点不是这个。考点可能是在面试过程中，面试官可能会用 449 作为follow up.
普通做法：没有用的BST 特征

1. public class Codec {
   
2.     private final static char SP=',';
   
3.     private final static char EMPTY='#';
   
4.     // Encodes a tree to a single string.
   
5.     public String serialize(TreeNode root) {
   
6.         StringBuilder sb= new StringBuilder();
   
7.         if(root == null) return "";
   
8.         Stack<TreeNode> stack = new Stack<>();
   
9.         stack.push(root);
   
10.         while(!stack.isEmpty()){
    
11.             TreeNode curr = stack.pop();
    
12.             if(curr == null){
    
13.                 sb.append(EMPTY);
    
14.             }else{
    
15.                 sb.append(curr.val);
    
16. 
    
17.                 stack.push(curr.right);
    
18.                 stack.push(curr.left);
    
19.             }
    
20.             
    
21.             sb.append(SP);
    
22.         }
    
23.         
    
24.         sb.deleteCharAt(sb.length()-1);
    
25.         return sb.toString();
    
26.     }
    
27. 
    
28.     // Decodes your encoded data to tree.
    
29.     public TreeNode deserialize(String data) {
    
30.         if(data == null || data.length() == 0) return null;
    
31.         String array[] = data.split("\\" + SP);
    
32.         Queue<String> queue = new LinkedList<>();
    
33.         for(String val: array){
    
34.             queue.add(val);
    
35.         }
    
36.         
    
37.         return deserializeHelper(queue);
    
38.     }
    
39.    
    
40.     public TreeNode deserializeHelper(Queue<String> queue){
    
41.         if(queue.isEmpty()) return null;
    
42.         String valStr = queue.remove();
    
43.         if(valStr.equals("" + EMPTY)) return null;
    
44.         int val = Integer.valueOf(valStr);
    
45.         TreeNode root = new TreeNode(val);
    
46.         root.left = deserializeHelper(queue);
    
47.         root.right = deserializeHelper(queue);
    
48.         
    
49.         return root;
    
50.         
    
51.     }
    
52. }

复制代码

用的BST 拍好序的特征：代码相对简洁一些,不需要存空叶子的值,而是利用preOrder和inorder的性质去实现

1. public class Codec {
   
2.     private final static char SP=',';
   
3.     // Encodes a tree to a single string.
   
4.     public String serialize(TreeNode root) {
   
5.         StringBuilder sb= new StringBuilder();
   
6.         if(root == null) return "";
   
7.         Stack<TreeNode> stack = new Stack<>();
   
8.         stack.push(root);
   
9.         while(!stack.isEmpty()){
   
10.             TreeNode curr = stack.pop();
    
11.             sb.append(curr.val).append(SP);
    
12.             if(curr.right!=null) stack.push(curr.right);
    
13.             if(curr.left !=null) stack.push(curr.left);
    
14.             
    
15.         }
    
16.         
    
17.         sb.deleteCharAt(sb.length()-1);
    
18.         return sb.toString();
    
19.     }
    
20. 
    
21.     // Decodes your encoded data to tree.
    
22.     public TreeNode deserialize(String data) {
    
23.         if(data == null || data.length() == 0) return null;
    
24.         String array[] = data.split("\\" + SP);
    
25.         Queue<Integer> queue = new LinkedList<>();
    
26.         for(String val: array){
    
27.             queue.add(Integer.valueOf(val));
    
28.         }
    
29.         
    
30.         return deserializeHelper(queue);
    
31.     }
    
32.    
    
33.     public TreeNode deserializeHelper(Queue<Integer> queue){
    
34.         if(queue.isEmpty()) return null;
    
35.         Integer curr = queue.remove();
    
36.    
    
37.         Queue<Integer> smallerQueue = new LinkedList<>();
    
38.         while(!queue.isEmpty() && queue.peek() < curr){
    
39.             smallerQueue.add(queue.remove());
    
40.         }
    
41.         
    
42.         TreeNode root = new TreeNode(curr);
    
43.         root.left = deserializeHelper(smallerQueue);
    
44.         root.right = deserializeHelper(queue);
    
45.         
    
46.         return root;
    
47.         
    
48.     }
    
49. }
    

复制代码