Javascript solution(but too slow)


  • 0
    T

    I use something like "1(2,3(4,5))" to represent the binary tree, but it seems that it is too slow...Is there anyway to improve the performance?

     /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    
    /**
     * Encodes a tree to a single string.
     *
     * @param {TreeNode} root
     * @return {string}
     */
    var serialize = function(root) {
        var result = "";
        var generate = function(node) {
            result += node.val;
            if(!node.left && !node.right) {
                return;
            }
            result += "(";
            if(!node.left) {
                result += "null";
            } else {
                generate(node.left);
            }
            result += ",";
            if(!node.right) {
                result += "null";
            } else {
                generate(node.right);
            }
            result += ")";
        }
        
        if(!root) {
            return "";
        } else {
            generate(root);
        }
       
        return result;
    };
    
    /**
     * Decodes your encoded data to tree.
     *
     * @param {string} data
     * @return {TreeNode}
     */
    var deserialize = function(data) {
        if(data.length === 0) {
            return [];
        }
        
        var root = new TreeNode(Number(data.split("(")[0]));
        var currentNode = root;
        
        for(var i=data.split("(")[0].length;i<data.length;i++) {
            if(data[i] === "(") {
                var subNode = new TreeNode(Number(data.substr(i+1).split(/[^0-9]/)[0]));
                currentNode.left = subNode;
                subNode.previous = currentNode;
                currentNode = subNode;
            } else if(data[i] === ",") {
                currentNode = currentNode.previous;
                var subNode = new TreeNode(Number(data.substr(i+1).split(/[^0-9]/)[0]));
                currentNode.right = subNode;
                subNode.previous = currentNode;
                currentNode = subNode;
            } else if(data[i] === ")") {
                currentNode = currentNode.previous;
            } else {
                continue;
            }
        }
        
        return root;
    };
    
    /**
     * Your functions will be called as such:
     * deserialize(serialize(root));
     */

Log in to reply
 

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