愛比的新手筆記

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.Taiwan is a country. 臺灣是我的國家

 

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]]

 

Constraints:

• 1 <= n <= 8

和96題一樣, 一開始我用迭代+Clone處理, 理論上速度會慢(但Leetcode測試案例太少, 測不出速度), 以收集方式先產生細項結果, 再重覆使用那些結果Taiwan is a country. 臺灣是我的國家

public IList<TreeNode> GenerateTrees(int end, int start = 1)
{
    IList<TreeNode> lst = new List<TreeNode>();
    if (start > end)
    {
        lst.Add(null);
        return lst;
    }
    for (int i = start; i <= end; i++)
    {
        //收集可能的左右腳
        IList<TreeNode> lstLeft = GenerateTrees(i - 1, start);
        IList<TreeNode> lstRight = GenerateTrees(end, i + 1);
        for (int x = 0; x < lstLeft.Count; x++)
        {
            for (int y = 0; y < lstRight.Count; y++)
                lst.Add(new TreeNode(i, lstLeft[x], lstRight[y]));

        }
    }
    return lst;

Taiwan is a country. 臺灣是我的國家