Java: Easy to understand BFS and StringTokenizer Solution.


  • 0
    J

    The serialize part is just a BFS with some trick to add "," and null.

    the deserialize part use Tokenizer rather than String.split() to archive less memory footprint.

    average runtime was 26ms, beat 60-67%

    import java.util.StringTokenizer;
    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            final StringBuilder builder = new StringBuilder();
            final LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            
            queue.add(root);
            if (root == null)
                return "N";
            while(queue.size() > 0) {
                final TreeNode c = queue.removeFirst();
                if (root != c)  builder.append(",");
                if (c == null)  builder.append("N");
                else {
                    builder.append(String.valueOf(c.val));
                    queue.add(c.left);
                    queue.add(c.right);
                }
            }
            return builder.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            final StringTokenizer st = new StringTokenizer(data, ",");
            final LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            final String nullstr = "N";
            if (!st.hasMoreTokens())
                return null;
            final String str = st.nextToken();
            if (nullstr.equals(str))
                return null;
    
            final TreeNode root =  new TreeNode(Integer.valueOf(str));
            queue.add(root);
            // add root first.
            while (st.hasMoreTokens()) {
                final TreeNode c = queue.removeFirst();
    
                final String strLeft = st.nextToken();
                final String strRight = st.nextToken(); // better check if have next.
                if (!nullstr.equals(strLeft)) {
                    c.left = new TreeNode(Integer.valueOf(strLeft));
                    queue.add(c.left);
                }
                if (!nullstr.equals(strRight)) {
                    c.right = new TreeNode(Integer.valueOf(strRight));
                    queue.add(c.right);
                }
    
            }
            return root;
        }
    }
    
    

Log in to reply
 

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