Java easy to understand solution with queue


  • 0
    D
    //Analysis: BFS for serialize, use queue and comma. Serialize is direct - add all left and right in the queue even it's null. Deserialize also uses a queue and only deals with none "#". 
    
    public String serialize(TreeNode root) {
        if(root == null){
            return "";
        }
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        StringBuilder sb = new StringBuilder();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                sb.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }else{
                sb.append("#,");
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
    
    
    public TreeNode deserialize(String data) {
        if(data == null || "".equals(data)){
            return null;
        }
        String[] strArr = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(strArr[0]));
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(!"#".equals(strArr[i])){
                TreeNode left = new TreeNode(Integer.parseInt(strArr[i]));
                node.left = left;
                queue.add(left);
            }
            i++;
            
            if(!"#".equals(strArr[i])){
                TreeNode right = new TreeNode(Integer.parseInt(strArr[i]));
                node.right = right;
                queue.add(right);
            }
            i++;
        }
        return root;
    }

Log in to reply
 

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