LeetCode 95.Unique Binary Search Trees II

Unique Binary Search Trees II : 題定一個數字 n，在 1 到 n的範圍內建立所有的二元搜尋樹(binary search trees)

Python

1.判斷邊界情況，如果n=0，則返回空樹。

2.使用遞歸函數generateTreesHelper(start,end)，它的作用是構造一棵以[start,end]的範圍內的節點為根節點的二叉搜索樹。

3.判斷當前子樹是否為空樹，如果是空樹就返回None，因為對於沒有節點的子樹就是空樹

4.使用循環遍歷start到end的所有可能的根節點, 每次選取一個i為根節點,以i為根節點，遞歸構造左子樹[start, i-1], 右子樹[i+1, end]

5.枚舉左右子樹的所有組合,將其連接在根節點上, 得到所有根節點為i的所有可能的二叉搜索樹

6.回溯，返回所有以1~n為根節點的二叉樹

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0:
            return []
        return self.generateTreesHelper(1, n)

    def generateTreesHelper(self, start: int, end: int) -> List[TreeNode]:
        if start > end:
            return [None]
        all_trees = []
        for i in range(start, end + 1):
            left_trees = self.generateTreesHelper(start, i - 1)
            right_trees = self.generateTreesHelper(i + 1, end)
            for left in left_trees:
                for right in right_trees:
                    root = TreeNode(i)
                    root.left = left
                    root.right = right
                    all_trees.append(root)
        return all_trees

C++

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) {
            return {};
        }
        return generateTrees(1, n);
    }

private:
    vector<TreeNode*> generateTrees(int start, int end) {
        if (start > end) {
            return {nullptr};
        }
        vector<TreeNode*> res;
        for (int i = start; i <= end; ++i) {
            vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
            vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
            for (const auto& leftTree : leftTrees) {
                for (const auto& rightTree : rightTrees) {
                    TreeNode* root = new TreeNode(i);
                    root->left = leftTree;
                    root->right = rightTree;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

Python

C++

相關