easy understand bfs solution without recursive 27ms


  • 1
    O

    ···
    //bfs encode , bfs decode
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
    if (root == null) return "#";

    	StringBuffer ret = new StringBuffer();
    	
    	LinkedList<TreeNode> queue = new LinkedList<>();
    	queue.addLast(root);
    	ret.append(root.val).append(",");
    
    	while (!queue.isEmpty()) {
    		TreeNode cur = queue.removeFirst();
    		if (cur.left  != null) queue.add(cur.left );
    		if (cur.right != null) queue.add(cur.right);
    		ret.append(cur.left  == null ? "#" : cur.left.val ).append(",");
    		ret.append(cur.right == null ? "#" : cur.right.val).append(",");
    	}
    	//remove '#' in the back of the sequence
    	int pos = ret.length() - 2;
    
    	for (; pos >= 0; pos -= 2)
    		if (ret.charAt(pos) != '#') break;
    
    	return ret.substring(0, pos + 1);
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
    	
        String[] seq = data.split(",");
        int pos = 0;
        TreeNode root = createNode(seq[pos ++]);
       
        LinkedList<TreeNode> queue = new LinkedList<>();
        if(root != null) queue.addLast(root);
        
    	while (!queue.isEmpty()) {
    		TreeNode cur = queue.removeFirst();
    		
    		if (pos < seq.length) //left child
    			cur.left = createNode(seq[pos++]);
    		if (cur.left != null)  queue.addLast(cur.left);
    		 
    		if (pos < seq.length)// right child
    			cur.right = createNode(seq[pos++]);
    		if (cur.right != null) queue.addLast(cur.right);
    		
    	}
        return root;
    }
    public TreeNode createNode(String val)
    {
    	if( val.equals("#") ) return null;
    	return new TreeNode(Integer.parseInt(val));
    }
    

    ···


Log in to reply
 

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