JavaScript DP solution that doesn't create right subtrees


  • 0
    R

    The key aspect of this DP solution is the binary tree property, where the highest node is always on the right.

    So generate the tree T(level-1), and for each node N:

    • Create a new TreeNode(level) and insert N on the left (any element on T(level-1) will always be less than level)
    • For each right node R of N, create a new TreeNode(level) and insert between the current node and R. See the comments bellow for an illustration.
    var copy = function(node) {
        if (!node) return node;
        let result = new TreeNode(node.val);
        result.left = copy(node.left);
        result.right = copy(node.right);
        return result;
    };
    
    var generateTrees = function(n) {
        let levels = [null, [new TreeNode(1)]];
        for (let i = 2; i <= n; i++) {
            let curLevel = levels[i] = [];
            levels[i-1].forEach(item => {
                // Every tree from generateTrees(n-1) is less
                // than i, because this is a binary tree
                let tmp = new TreeNode(i);
                tmp.left = copy(item);
                curLevel.push(tmp);
    
                // Let's copy the current tree from generateTrees(n-1)
                // 1
                //   \
                //     2
                //       \
                //         3
                // Then for each level, let's insert a new node TreeNode(i) on the right,
                // and move the old right to the left of the new node
                // 1        1          1
                //   \        \          \
                //   (4)        2          2
                //    /           \          \
                //  2             (4)          3
                //   \            /             \
                //     3        3               (4)
                // 
                // To avoid having to walk the right nodes every time (1 for the first level,
                // 2 for the second level, and so on), we copy the source node and then modify
                // it in place! So each iteration of this loop will generate a new solution.
                let source = copy(item);
                let node = source;
                while (node) {
                    // Store the previous right subtree
                    let oldRight = node.right;
                    
                    // The new right subtree starts with the current level node
                    node.right = new TreeNode(i);
                    
                    // The old right subtree must be less than the current node,
                    // so we just put it on the left
                    node.right.left = oldRight;
                    
                    // Save the tree as it's now, because it's a solution
                    curLevel.push(copy(source));
                    
                    // Restore the old ordering
                    node.right = oldRight;
                    
                    // And finally do the same for the (old) right subtree
                    node = node.right;
                }
            });
        }
        return levels[n];
    };
    
    
    

Log in to reply
 

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