Short and straight forward BFS Java code with a queue


  • 66

    Here I use typical BFS method to handle a binary tree. I use string n to represent null values. The string of the binary tree in the example will be "1 2 3 n n 4 5 n n n n ".

    When deserialize the string, I assign left and right child for each not-null node, and add the not-null children to the queue, waiting to be handled later.

    public class Codec {
        public String serialize(TreeNode root) {
            if (root == null) return "";
            Queue<TreeNode> q = new LinkedList<>();
            StringBuilder res = new StringBuilder();
            q.add(root);
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                if (node == null) {
                    res.append("n ");
                    continue;
                }
                res.append(node.val + " ");
                q.add(node.left);
                q.add(node.right);
            }
            return res.toString();
        }
    
        public TreeNode deserialize(String data) {
            if (data == "") return null;
            Queue<TreeNode> q = new LinkedList<>();
            String[] values = data.split(" ");
            TreeNode root = new TreeNode(Integer.parseInt(values[0]));
            q.add(root);
            for (int i = 1; i < values.length; i++) {
                TreeNode parent = q.poll();
                if (!values[i].equals("n")) {
                    TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                    parent.left = left;
                    q.add(left);
                }
                if (!values[++i].equals("n")) {
                    TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                    parent.right = right;
                    q.add(right);
                }
            }
            return root;
        }
    }

  • 1
    Y

    how to eliminate the 4 trailing ns in "1 2 3 n n 4 5 n n n n "?


  • 0
    Z

    for (int i = 1; i < values.length - 1; i++) , because split creates an extra empty value from the last delimiter


  • 1
    D

    I've got a question for this, which is although this passes the Online Judgement, it can't pass my own test case, since

     q.add(node.left);
    

    causes NullPointerException, if node.left is null.

    So my question is does this

    Queue<TreeNode> q = new LinkedList<>();
    

    allow null TreeNode or not?


  • 2
    C

    Same BFS. I used "boolean left" to save some repeat code in deserialize part.
    public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode cur=q.poll();
            if(cur==null) {
                sb.append("n,");
                continue;
            }
            sb.append(cur.val+",");
            TreeNode temp=cur.left;
            q.add(temp);
            temp=cur.right;
            q.add(temp);
        }
        return sb.toString();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes=data.split(",");
        boolean left=true;
        if(nodes.length==0||nodes[0].equals("n")) return null;
        TreeNode root=new TreeNode(Integer.valueOf(nodes[0])),cur=root;
        Queue<TreeNode> q = new LinkedList<>();
        for(int i=1;i<nodes.length;i++){
             
            if(!nodes[i].equals("n")){
                TreeNode temp=new TreeNode(Integer.valueOf(nodes[i]));
                if(left) cur.left=temp;
                else cur.right=temp;
                q.add(temp);
            }
            left=!left;
            if(left&&!q.isEmpty())
                cur=q.poll();
        }
        return root;
    }
    

    }


  • 0
    M

    @D_shaw LinkedList allows null nodes. Quoted from https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

    Queue implementations generally do not allow insertion of null elements, although some implementations, such as LinkedList, do not prohibit insertion of null. Even in the implementations that permit it, null should not be inserted into a Queue, as null is also used as a special return value by the poll method to indicate that the queue contains no elements.


  • 0
    J

    I think there could some space optimization for serialization. There could be many null TreeNode at the end of String. I think we could remove them all to save some space.


  • 1

    @yangji1993 Use a LinkedList to store the values, while using these two lines as the last two lines of serialize:

    while (result.peekLast() == null && !result.isEmpty()) result.removeLast();
    return result.toString();
    

    It gives you the official representation of a binary tree.


  • 0
    L

    Good idea, this is C++ version

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string serialization = "";
            queue<TreeNode*> qq;
            qq.push(root);
            while(!qq.empty()){
                TreeNode * cur = qq.front();
                qq.pop();
                if(cur != NULL){
                    serialization += to_string(cur -> val) + ',';
                    qq.push(cur -> left);
                    qq.push(cur -> right);
                }
                else serialization += "X,";
            }
            return serialization;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            vector<string> vals;
            while(!data.empty()){
                string temp = "";
                temp = data.substr(0, data.find_first_of(','));
                vals.push_back(temp);
                data = data.substr(data.find_first_of(',') + 1);
            }
            if(vals[0] == "X") return NULL;
            queue<TreeNode*> q;
            TreeNode* root = NULL;
            root = new TreeNode(stoi(vals[0]));
            q.push(root);
            for(int i = 1; i < vals.size(); ++i){
                TreeNode* parent = q.front();
                q.pop();
                if(vals[i] != "X"){
                    parent -> left = new TreeNode(stoi(vals[i]));
                    q.push(parent -> left);
                }
                i++;//no matter add a new node or not the i should be i + 1
                if(vals[i] != "X"){
                    parent -> right = new TreeNode(stoi(vals[i]));
                    q.push(parent -> right);
                }
            }
            return root;
        }
    };
    
    

  • 2

    Same BFS. But I delete the None nodes in the end. I think this is important because if we don't do it, the length of the string after serialization would be twice as long in the worst case (the tree is perfect). And also we double the workload in the deserialization process.

    from collections import deque
    class Codec:
    
        def serialize(self, root):
            if not root:
                return ''
    
            queue = deque()
            queue.append(root)
            res = [str(root.val)]
            
            while queue:
                l = len(queue)
                for _ in range(l):
                    node = queue.popleft()
                    for child in [node.left, node.right]:
                        if child:
                            queue.append(child)
                            res.append(str(child.val))
                        else:
                            res.append('#')
            while res[-1] == '#':
                res.pop()
            return ' '.join(res)
    
        def deserialize(self, data):
            if data == '':
                return None
            cache = data.split(' ')
    
            root = TreeNode(int(cache[0]))
            queue = deque()
            queue.append(root)
            i = 1
    
            while queue and i < len(cache):
                l = len(queue)
                for _ in range(l):
                    node = queue.popleft()
    
                    if i < len(cache) and cache[i] != '#':
                        left = TreeNode(int(cache[i]))
                        node.left = left
                        queue.append(left)
                    i += 1
    
                    if i < len(cache) and cache[i] != '#':
                        right = TreeNode(int(cache[i]))
                        node.right = right
                        queue.append(right)
                    i += 1
            return root
    

  • 0
    S

    @BetaGoGoGo Twice? Are you sure?


  • 0
    T

    Exactly the same thought but with a slightly differnt solution:

    public String serialize(TreeNode root) {
        if( root == null ) return "";
        
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while( !queue.isEmpty() ){
            
            TreeNode temp = queue.poll();
            if( temp == null ){
                sb.append(" null");
                continue;
            }
            else{
                sb.append(" ");
                sb.append(String.valueOf(temp.val));
            }
            
            queue.add(temp.left);
            queue.add(temp.right);
        }
        
        return sb.toString().trim();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if( data == null || data.length() <=0 ) return null;
        
        String[] strArray = data.split(" ");
        int count = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        
        TreeNode result = new TreeNode(Integer.parseInt(strArray[0]));
        queue.add(result);
        count++;
        
        while( !queue.isEmpty() ){
            TreeNode temp = queue.poll();
            if( !strArray[count].equals("null") ){
                TreeNode left = new TreeNode(Integer.parseInt(strArray[count]));
                temp.left = left;
                queue.add(left);                
            }
            count++;
            if( !strArray[count].equals("null") ){
                TreeNode right = new TreeNode(Integer.parseInt(strArray[count]));
                temp.right = right;
                queue.add(right);                
            }
            count++;
        }
        return result;
    }

Log in to reply
 

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