LeetCode 95. Unique Binary Search Trees II JavaScript solution

看到 Ｃ羅大哭真的感傷，英雄總有遲暮，每次退下不一定完美

分享給你活存2.6%的推薦連結，一般活存僅有0.3%～

2.6%回饋靠Bankee，讓我們的故事從Bankee開始！

Unique Binary Search Trees II - LeetCode

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
  if (n==0) return [];
    
    const createTreeNode = (start, end) => {
        
        if (start > end) return [undefined];
        const res = [];
    
        for (let i = start; i <= end; i++) {
            
            let leftTree = createTreeNode(start, i-1);
            let rightTree = createTreeNode(i+1, end);

            for (const curLeft of leftTree) {
                for (const curRight of rightTree) {
                    let rootNode = new TreeNode(i, curLeft, curRight);
                    res.push(rootNode);
                } 
            }  
        }
        return res;
    } 
    
    return createTreeNode(1, n);
};

i 為 root node，例如 i = 1 代表將 [1 | 2, 3] 切分為 root i，createTreeNode(left node= null)，createTreeNode(right node=[2, 3])，right node 遞迴，需要分別跑 i = 2, 3 的情況，當 i = 2 = root node，將 3 分為 right node [2 | 3] ，當 i = 3 = root node，將 2分為 right node [2 | 3]，因此結果是會是 [1,null,2,null,3],[1,null,3,2]，如下圖最左邊兩圖

leftTree 是左子樹所有可能，rightTree 是右子樹所有可能，需要將所有可能組合後回傳。

美國舊金山 大聯盟奧克蘭運動家 金門大橋遊艇 USA — San Fransisco / FunkyGary / sunflower — post malone