Recursive JavaScript Solution


  • 0
    W

    This solution has a few logical steps. We create a tree and validate it along the way, checking for remaining nodes afterward. Possibly there are better solutions but this is what came to my mind!

    • Create an array of nodes from the string
      • If the number of nodes is even, it's an invalid tree and we can fail early
    • Begin building a tree via a simple object
      • If a node doesn't have children, fail
      • Otherwise, build node children recursively until # (null)
    • If there are floating nodes remaining after building the tree, fail
    /**
     * @param {string} preorder
     * @return {boolean}
     */
    var isValidSerialization = function(preorder) {
        let nodes = preorder.split(',');
        if (nodes.length % 2 === 0) return false;
        let tree = buildTree(nodes.shift(), nodes);
        return !(tree === false || nodes.length > 0);
    };
    
    var buildTree = function(r, nodes) {
        let root = { val: r };
        if (r == '#') return root;
        let left = { val: nodes.shift() };
        let right = { val: nodes.shift() };
        if (left.val == null || right.val == null) return false;
        if (left.val != '#') {
            left = buildTree(left.val, nodes);
        }
        if (right.val != '#') {
            right = buildTree(right.val, nodes);
        }
        root.left = left;
        root.right = right;
        return root;
    }
    

Log in to reply
 

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