leetcode 449. Serialize and Deserialize BST | 449. 序列化和反序列化二叉搜索树（BST后序遍历性质）

小鱼儿 2022-09-05 00:27 125阅读 0赞

## 题目 ##

[https://leetcode.com/problems/serialize-and-deserialize-bst/][https_leetcode.com_problems_serialize-and-deserialize-bst]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

本题的难点在于 **利用 BST 的性质**。

##### 几个提示 #####

*  根据后序遍历BST性质，头结点是最后一个元素，且有一个分界，满足比头结点小的都在左边，比头结点大的都在右边
 *  本题满足条件（但是题目中没说）没有重复值
 *  要求你返回的树的形状不仅是 BST，而且要与输入完全相同。同样是 BST，注意以下两树的区别。它们中序序列相同，后序序列不同。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

##### 对比 #####

一开始我想，这不就是序列化/反序列化一棵普通树吗？只不过给你的时候恰好是 BST。这和 [297. Serialize and Deserialize Binary Tree][] 有什么不同？

再一想，不一样。利用二叉树的性质，可以将序列化结果简化，也就是本题说的 **The encoded string should be as compact as possible. 编码的字符串应尽可能紧凑**。

参考左神算法书 P107 “二叉树的序列化和反序列化”，他在序列化一棵普通树的时候，利用了先序遍历的方式，用 \# 记录空节点。而本题是 BST，其本身性质决定了不需要通过 \# 记录空节点，也能进行 **唯一结果的** 序列化与反序列化。

附从错误思路到正确思路的草稿：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Codec { 
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) { 
            if (root == null) return "";
    
            StringBuilder s = new StringBuilder();
            postOrder(root, s);
            return s.substring(0, s.length() - 1); // 移除末尾 ','
        }
        
        public void postOrder(TreeNode node, StringBuilder s) { 
            if (node == null) return;
    
            postOrder(node.left, s);
            postOrder(node.right, s);
            s.append(node.val).append(",");
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) { 
            if (data.equals("")) return null;
    
            String[] ss = data.split(",");
            int[] arr = new int[ss.length];
            for (int i = 0; i < ss.length; i++) { 
                arr[i] = Integer.parseInt(ss[i]);
            }
            return buildBST(arr, 0, arr.length - 1);
        }
        
        // 根据后序遍历BST性质，头结点是最后一个元素，且有一个分界，满足比头结点小的都在左边，比头结点大的都在右边
        public TreeNode buildBST(int[] arr, int L, int R) { 
            if (L > R) return null;
            TreeNode node = new TreeNode(arr[R]);
            // 找左右子树的分界点
            int M = L;
            while (arr[M] < arr[R]) { 
                M++;
            }
            // M指向分界点右边第一个元素，本题缺隐含条件：没有重复值！
            node.left = buildBST(arr, L, M - 1);
            node.right = buildBST(arr, M, R - 1);
            return node;
        }
    }
    
    
    // Your Codec object will be instantiated and called as such:
    // Codec ser = new Codec();
    // Codec deser = new Codec();
    // String tree = ser.serialize(root);
    // TreeNode ans = deser.deserialize(tree);
    // return ans;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]

##### 可参考：左程云《程序员代码面试指南》根据后序数组重建搜索二叉树 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 6]

package chapter_3_binarytreeproblem;
    
    public class Problem_14_PosArrayToBST { 
    
    	public static boolean isPostArray(int[] arr) { 
    		if (arr == null || arr.length == 0) { 
    			return false;
    		}
    		return isPost(arr, 0, arr.length - 1);
    	}
    
    	public static boolean isPost(int[] arr, int start, int end) { 
    		if (start == end) { 
    			return true;
    		}
    		int less = -1;
    		int more = end;
    		for (int i = start; i < end; i++) { 
    			if (arr[end] > arr[i]) { 
    				less = i;
    			} else { 
    				more = more == end ? i : more;
    			}
    		}
    		if (less == -1 || more == end) { 
    			return isPost(arr, start, end - 1);
    		}
    		if (less != more - 1) { 
    			return false;
    		}
    		return isPost(arr, start, less) && isPost(arr, more, end - 1);
    	}
    
    	public static class Node { 
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int value) { 
    			this.value = value;
    		}
    	}
    
    	public static Node posArrayToBST(int[] posArr) { 
    		if (posArr == null) { 
    			return null;
    		}
    		return posToBST(posArr, 0, posArr.length - 1);
    	}
    
    	public static Node posToBST(int[] posArr, int start, int end) { 
    		if (start > end) { 
    			return null;
    		}
    		Node head = new Node(posArr[end]);
    		int less = -1;
    		int more = end;
    		for (int i = start; i < end; i++) { 
    			if (posArr[end] > posArr[i]) { 
    				less = i;
    			} else { 
    				more = more == end ? i : more;
    			}
    		}
    		head.left = posToBST(posArr, start, less);
    		head.right = posToBST(posArr, more, end - 1);
    		return head;
    	}
    
    	// for test -- print tree
    	public static void printTree(Node head) { 
    		System.out.println("Binary Tree:");
    		printInOrder(head, 0, "H", 17);
    		System.out.println();
    	}
    
    	public static void printInOrder(Node head, int height, String to, int len) { 
    		if (head == null) { 
    			return;
    		}
    		printInOrder(head.right, height + 1, "v", len);
    		String val = to + head.value + to;
    		int lenM = val.length();
    		int lenL = (len - lenM) / 2;
    		int lenR = len - lenM - lenL;
    		val = getSpace(lenL) + val + getSpace(lenR);
    		System.out.println(getSpace(height * len) + val);
    		printInOrder(head.left, height + 1, "^", len);
    	}
    
    	public static String getSpace(int num) { 
    		String space = " ";
    		StringBuffer buf = new StringBuffer("");
    		for (int i = 0; i < num; i++) { 
    			buf.append(space);
    		}
    		return buf.toString();
    	}
    
    	public static void main(String[] args) { 
    		int[] arr = {  2, 1, 3, 6, 5, 7, 4 };
    		System.out.println(isPost(arr, 0, arr.length - 1));
    		printTree(posArrayToBST(arr));
    	}
    }

[https_leetcode.com_problems_serialize-and-deserialize-bst]: https://leetcode.com/problems/serialize-and-deserialize-bst/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/ad037f7518fa498e9b0889fe8e2d5d87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/7eb52b3909b245cd8241a7a3d84a6947.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/19a59bb2f85748438010d25532e6e0bf.png
[297. Serialize and Deserialize Binary Tree]: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20220829/4b492ce1e4aa4ae9a28c5e7ec0abdc00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]: /images/20220829/2216518f0e2f42e49c51ae0600d7288d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 5]: /images/20220829/4cf9f0dbd0b7491f89ac6e8d670cd34b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 6]: /images/20220829/86afe9b9b7fb4ceb9b3632c4eac44c85.png