Is it possible to get an O(1) space O(n) time algorithm?


  • 0
    S

    Here is my O(n)-O(n) solution, tl;dr

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null)
            return "N#";
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        StringBuffer sb = new StringBuffer();
    
        q.add(root);
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode t = q.remove();
                if (t == null) {
                    sb.append("N#");
                }
                else {
                    sb.append(Integer.toString(t.val) + "#");
                    q.add(t.left);
                    q.add(t.right);
                }
            }
        }
        return sb.toString();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.charAt(0) == 'N')
            return null;
    
        int index = data.indexOf('#');
        Queue<TreeNode> q = new LinkedList<TreeNode>();
    
        TreeNode root = new TreeNode(Integer.parseInt(data.substring(0, index)));
        q.add(root);
        index += 1;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode t = q.remove();
                // left child
                if (data.charAt(index) == 'N') {
                    index += 2;
                } else {
                    int next_index = data.indexOf('#', index);
                    TreeNode l = new TreeNode(Integer.parseInt(data.substring(index, next_index)));
                    index = next_index + 1;
                    t.left = l;
                    q.add(l);
                }
                // right child
                if (data.charAt(index) == 'N') {
                    index += 2;
                } else {
                    int next_index = data.indexOf('#', index);
                    TreeNode r = new TreeNode(Integer.parseInt(data.substring(index, next_index)));
                    index = next_index + 1;
                    t.right = r;
                    q.add(r);
                }
            }
        }
        return root;
    }
    

    Is it possible to avoid using a queue or i missed some existing post?


Log in to reply
 

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