Serialize and Deserialize Binary Tree

• 推荐方法

Java

public class Seri {

	String result="";
	int id=0;
	private int serialWork(TreeNode root){
		if (root==null) return -1;
		id++;
		int nowId=id;
		int leftId=serialWork(root.left);
		int rightId=serialWork(root.right);
		result+=root.val+","+nowId+","+leftId+","+rightId+";";
		return nowId;
	}


	public String serialize(TreeNode root) {
		// write your code here
		int rootId=serialWork(root);
		return result;
	}

	public TreeNode deserialize(String data) {
		// write your code here
		String[] nodes=data.split(";");
		HashMap<Integer,TreeNode> nodeHashMap=new HashMap<Integer, TreeNode>();
		for (int i=0;i<nodes.length;i++){
			String[] datas=nodes[i].split(",");
			if (datas.length!=4) continue;
			if (!nodeHashMap.containsKey(Integer.parseInt(datas[1]))) {
				TreeNode node = new TreeNode(Integer.parseInt(datas[0]));
				nodeHashMap.put(Integer.parseInt(datas[1]), node);
			}
			else{
				nodeHashMap.get(Integer.parseInt(datas[1])).val=Integer.parseInt(datas[0]);
			}
			if (!nodeHashMap.containsKey(Integer.parseInt(datas[2])) && Integer.parseInt(datas[2])!=-1){
				nodeHashMap.put(Integer.parseInt(datas[2]),new TreeNode(-1));
			}
			if (!nodeHashMap.containsKey(Integer.parseInt(datas[3])) && Integer.parseInt(datas[3])!=-1){
				nodeHashMap.put(Integer.parseInt(datas[3]),new TreeNode(-1));
			}
			nodeHashMap.get(Integer.parseInt(datas[1])).left=nodeHashMap.get(Integer.parseInt(datas[2]));
			nodeHashMap.get(Integer.parseInt(datas[1])).right=nodeHashMap.get(Integer.parseInt(datas[3]));
		}

		return nodeHashMap.get(1);
	}
}

• 其他方法

Java

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("N");
            } else {
                sb.append(node.val);
                queue.offer(node.left);
                queue.offer(node.right);
            }
            sb.append("#");
        }
        sb.setLength(sb.length() - 1);
        // System.out.println(sb);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split("#");
        if (strs.length == 1 && "N".equals(strs[0])) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int i = 1;
        while (i < strs.length) {
            TreeNode node = queue.poll();
            if (!"N".equals(strs[i])) {
                node.left = new TreeNode(Integer.parseInt(strs[i]));
                queue.offer(node.left);
            }
            i++;
            if (!"N".equals(strs[i])) {
                node.right = new TreeNode(Integer.parseInt(strs[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

Python

from collections import deque
def serialize(self, root):
    dq = deque([root])
    ans = []
    while dq:
        node = dq.popleft()
        if node:
            ans.append(str(node.val))
            dq.append(node.left)
            dq.append(node.right)
        else:
            ans.append('')
    while ans and not ans[-1]:
        ans.pop()
    return ','.join(ans)

def deserialize(self, data):
    if not data:
        return None
    nodes = map(lambda s: None if not s else TreeNode(int(s)), data.split(','))
    nodes.reverse()
    root = nodes.pop()
    dq = deque([root])
    while nodes:
        node = dq.popleft()
        node.left = nodes.pop()
        if node.left:
            dq.append(node.left)
        if not nodes:
            break
        node.right = nodes.pop()
        if node.right:
            dq.append(node.right)
    return root