95. Unique Binary Search Trees II

Leetcode

https://leetcode.com/problems/unique-binary-search-trees-ii/

題目

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

Input: n = 1
Output: [[1]]

前置知識

Binary Search Tree (BST) 是一種符合以下幾種特性的資料結構：

1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；

2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；

3. 任意節點的左、右子樹也分別為二元搜尋樹；

簡單來說就是 樹的左邊比根節點小，數的右邊比根節點大

解答

• 方法一 - 遞迴

要求出從 1~n 所有可能的 BST，如果從根節點來看的話會有以下幾種可能：

1. 根節點為 1：

左子樹為 []，右子樹為 [2, ..., n] 所有可能的 BST

1. 根節點為 2：

左子樹為 [1]，右子樹為 [3, ..., n] 所有可能的 BST

1. 根節點為 3：

左子樹為 [1, 2]，右子樹為 [4, ..., n] 所有可能的 BST

............

1. 根節點為 n：

左子樹為 [1, ..., n-1]，右子樹為 []

而子樹中所有可能的 BST，一樣可以按照上面的方式，先固定根節點的元素，在分成左右子樹尋找所有可能的組合

var generateTrees = function (n) {
    const buildTrees = (start, end) => {
        const trees = [];
        
        // 沒有左邊大於右邊的子樹，所以 push null
        if (start > end) {
            trees.push(null);
            return trees;
        }

        // 單一值的節點
        if (start === end) {
            const tree = new TreeNode(start);
            trees.push(tree);
            return trees;
        }

        // 從 start 開始將所有值當作根節點
        for (let i = start; i <= end; i++) {
            // 解釋1. 建構左子樹
            const leftTrees = buildTrees(start, i - 1);
            // 解釋2. 建構右子樹
            const rightTrees = buildTrees(i + 1, end);

            // 解釋3. 將左、右子樹兩兩配對
            for (let leftTree of leftTrees) {
                for (let rightTree of rightTrees) {
                    // 將左、右子樹配對的組合放在 root 底下
                    const root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    trees.push(root);
                }
            }
        }

        return trees;
    }

    return buildTrees(1, n);
};

Runtime: 73 ms Beats 64.57% of users with JavaScript

Memory: 56.48 MB Beats 60.54% of users with JavaScript

解釋

1. 建構左子樹

const leftTrees = buildTrees(start, i - 1);

假設 start=2, i=5，左子樹會是 [2, 3, 4] 組成的可能 BST

1. 建構右子樹

const rightTrees = buildTrees(i + 1, end);

假設 i=2, end=5，右子樹會是 [3, 4, 5] 組成的可能 BST

1. 將左、右子樹兩兩配對

假設 [1, 2, 3, 4, 5]，根節點為 3：

左子樹為 [1, 2]、右子樹為 [4, 5]，此組合下所有可能的 BST 有以下幾種：

     3            3          3           3
    / \          / \        / \         / \
   2   4        2   5      1   4       1   5
  /     \      /   /      /     \     /   /
 1       5    1   4      2       5   2   4

可以看到左邊是 [1, 2] 兩種可能性、右邊是 [4, 5] 兩種可能性，因此需要用雙層迴圈將左、右子樹兩兩配對後，再加入到 root 底下

參考資料

95*. Unique Binary Search Trees II · leetcodeleetcode.wang