Java Level Order (13 ms). no split, no parseInt, no substring, no equals


  • 0
    K

    public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        
        q.add(root);
        TreeNode next;
        
        while (!q.isEmpty()) {
            next = q.poll();
            if (next == null) {
                builder.append('x');
            } else {
                builder.append(next.val);
                q.add(next.left);
                q.add(next.right);
            }
            builder.append(' ');
        }
        return builder.toString();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String str) {
        int[] nextIndex = new int[1];
        TreeNode root = decode(str, 0, nextIndex);
        
        if (root == null) {
            return null;
        }
        
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode last, left, right;
        q.add(root);
    
        while (nextIndex[0] < str.length()) {
            last = q.poll();
            
            left = decode(str, nextIndex[0], nextIndex);
            right = decode(str, nextIndex[0], nextIndex);
            
            if (left != null) {
                q.add(left);
            }
            if (right != null) {
                q.add(right);
            }
            
            last.left = left;
            last.right = right;
        }
        return root;
    }
    
    private TreeNode decode(String str, int start, int[] nextIndex) {
        if (str.charAt(start) == 'x') {
            nextIndex[0] = start + 2;
            return null;
        }
        
        int val = 0;
        short sign = 1;
        
        if (str.charAt(start) == '-') {
            sign = -1;
            start++;
        }
        
        while (start < str.length() && str.charAt(start) != ' ') {
            val = val * 10 + (str.charAt(start++) - '0');
        }
        nextIndex[0] = start + 1;
        return new TreeNode(val * sign);
    }
    

    }


Log in to reply
 

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