题解 | #序列化二叉树#

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null;

public TreeNode(int val) {
    this.val = val;

}

} */ import java.util.Arrays; import java.util.LinkedList; import java.util.List;

public class Solution { String Serialize(TreeNode root) { if(root == null) return "";

	StringBuffer str = new StringBuffer();
	pre_dis(root, str);//先序遍历的结果加到字符串上
	str.append("+");
	in_dis(root, str);//中序遍历的结果加到字符串上
	
    return str.toString();
}

private void pre_dis(TreeNode root,StringBuffer s) {
	if(root == null) return;
	
	s.append(root.val + ",");
	pre_dis(root.left,s);
	pre_dis(root.right,s);
}

private void in_dis(TreeNode root,StringBuffer s) {
	if(root == null) return;
	
	in_dis(root.left,s);
	s.append(root.val + ",");
	in_dis(root.right,s);
}

TreeNode Deserialize(String str) {
    if(str.equals("")) return null;
    
   String[] split = str.split("\\+");
	List<Integer> list1 = new LinkedList<>();//先序遍历的结果
	List<Integer> list2 = new LinkedList<>();//中序遍历的结果
	for (int i = 0; i < split.length; i++) {
		String[] str1 = split[i].split(",");
		if(i == 0) {
			for(int j = 0;j < str1.length;j++) {
    			list1.add(Integer.parseInt(str1[j]));
    		}
		}
		if(i == 1) {
			for(int j = 0;j < str1.length;j++) {
    			list2.add(Integer.parseInt(str1[j]));
    		}
		}
	}
	
    //在变成数组
	int[] arr1 = new int[list1.size()];
	int[] arr2 = new int[list2.size()];
	for(int i = 0;i < arr1.length;i++) {
		arr1[i] = list1.get(i);
	}
	for(int i = 0;i < arr1.length;i++) {
		arr2[i] = list2.get(i);
	}
	
    return reConstructBinaryTree(arr1, arr2);//然后用前面jz7咱们写好的函数就行了
}

public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
	if(pre.length == 0) return null;
	TreeNode root = new TreeNode(pre[0]);
	
	int index = -1;
	for(int i = 0;i < vin.length;i++) {
		if(vin[i] == pre[0]) {
			index = i;
		}
	}
	
	int[] pre1 = Arrays.copyOfRange(pre, 1, index+1);
	int[] pre2 = Arrays.copyOfRange(pre, index+1, pre.length);
	int[] vin1 = Arrays.copyOfRange(vin, 0, index);
	int[] vin2 = Arrays.copyOfRange(vin, index+1, vin.length);
	
	root.left = reConstructBinaryTree(pre1, vin1);
	root.right = reConstructBinaryTree(pre2, vin2);
	
    return root;
}

}