My Java Solution Sharing


  • 0
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        StringBuilder sb = new StringBuilder();
        sb.append(Integer.toString(root.val) + ",");
        Queue<TreeNode> list = new LinkedList<>();
        list.offer(root);
        boolean keepgoing = true;
        while(!list.isEmpty() && keepgoing) {
            keepgoing = false;
            Queue<TreeNode> subList = new LinkedList<>();
            while(!list.isEmpty()) {
                TreeNode temp = list.poll();
                sb.append(temp.left == null ? "null," : Integer.toString(temp.left.val) + ",");
                sb.append(temp.right == null ? "null," : Integer.toString(temp.right.val) + ",");
                if(temp.left != null) {
                    subList.offer(temp.left);
                    if(temp.left.left != null || temp.left.right != null) keepgoing = true;
                }
                if(temp.right != null) {
                    subList.offer(temp.right);
                    if(temp.right.left != null || temp.right.right != null) keepgoing = true;
                }
            }
            list = subList;
        }
        return sb.subSequence(0, sb.length()-1).toString();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        String[] list = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(list[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode temp = root;
        for(int i=1; i<list.length; i++) {
            if(i%2 == 1) {
                temp = queue.poll();
                if(!list[i].equals("null")) {
                    temp.left = new TreeNode(Integer.parseInt(list[i]));
                    queue.offer(temp.left);
                }
            } else {
                if(!list[i].equals("null")) {
                    temp.right = new TreeNode(Integer.parseInt(list[i]));
                    queue.offer(temp.right);
                }
            }
        }
        return root;
    }
    

    Main idea:

    Use iterative BFS to store every level's tree node, and use a var keepgoing to decide whether there are any node in the next level.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.