449. 序列化和反序列化二叉搜索树 (opens new window)

1.二叉树恢复

解题思路：采用先序遍历进行序列化。反序列化时采用分段思想，找到数组中分别属于左子树和右子树的连续子数组。而如果进行划分一般分为以下几种情况：

• 根据前序遍历+中序遍历进行恢复：在前序遍历结果中定位根节点，然后从中序遍历划分。
• 仅给出前序遍历+二叉搜索树进行恢复：根据二叉搜索树性质左子树所有节点都小于根节点。

本题属于上面第②种类型。

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null) return "";
        String leftstr="";
        String rightstr="";
        if(root.left!=null) leftstr=serialize(root.left);
        if(root.right!=null) rightstr=serialize(root.right);
        return String.valueOf(root.val)+","+leftstr+rightstr;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0) return null;
        String[] tree=data.split(",");
        return parseTree(tree,0,tree.length-1);
        
    }
    public TreeNode parseTree(String[] tree,int start,int end){
        TreeNode root=new TreeNode(Integer.valueOf(tree[start]));
        if(start==end) return root;
        int rightstart=end+1;
        for(int i=start+1;i<=end;i++){
            int val=Integer.valueOf(tree[i]);
            if(val>root.val){
                rightstart=i;
                break;
            }
        }
        TreeNode left=null,right=null;
        if(rightstart>start+1) left=parseTree(tree,start+1,rightstart-1);
        if(rightstart<end+1) right=parseTree(tree,rightstart,end);
        root.left=left;
        root.right=right;
        return root;
    }
}

2.上下界思想优化

上述算法中，前序遍历数组同一个元素会被遍历多次。

假设存在这么一棵二叉搜素树【4，2，1，3，5】，我们可以规定上下界使元素构建时能够准确找到它的父节点。比如1在构建时他的父节点应该是2，而不是4。也就是说在元素2在构建完二叉树后，下一个元素在【-∞，2】才能作为2的左孩子插入，只有在【2，4】之间才能作为2的右孩子插入，而大于4的节点值显然只能作为4的右孩子进行构建。

具体来说，前一个节点需要作为左孩子的上界，右孩子的下界。下一个节点根据处在哪个上下界范围进行构建，时间复杂度O(n)

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null) return "";
        String leftstr="";
        String rightstr="";
        if(root.left!=null) leftstr=serialize(root.left);
        if(root.right!=null) rightstr=serialize(root.right);
        return String.valueOf(root.val)+","+leftstr+rightstr;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0) return null;
        String[] tree=data.split(",");
        List<Integer> list=new LinkedList<>();
        for(int i=0;i<tree.length;i++) list.add(Integer.valueOf(tree[i]));
        return parseTree(list,Integer.MIN_VALUE,Integer.MAX_VALUE);
    }
    public TreeNode parseTree(List<Integer> list,int lower,int upper){
        if(list.size()==0||list.get(0)>upper||list.get(0)<lower) return null;
        TreeNode root=new TreeNode(list.get(0));
        list.remove(0);
        root.left=parseTree(list,lower,root.val);
        root.right=parseTree(list,root.val,upper);
        return root;
    }
}