Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 思路：
: 1.因為要構建所有樹的可能，所以只能用dfs去遞迴所有結果，所以關鍵在遞迴結束條件。
: 2.一個 full BT 的子節點數量只能為 0 或 2 這表示當 n 為偶數時，不可能存在合法
:   的樹，返回空的 List。
: 3.full BT 的最小合法樹為 n = 1 只有根節點的情況，所以 n = 1 也直接返回。
: 4.當 n 為奇數時，我們可以先把根節點設置好，並把剩下的節點分給左右子樹去遞迴構
:   建，構建結果的左右子樹組合就是解。

Tree每次都要玩遞迴

好苦


這題主要是FBT的特性 可以只有左node不能只有右node

1. 先排除掉node偶數以及n=1的情況

2. 以及右側tree的數量是 n - 左側數量 - 1(root那個點)

3. 每次迴圈跑i都是在定義左邊tree有幾個，然後才考慮右邊tree的情況

最後就是一直家庭代工 把Tree接起來


class Solution
{
public:
    vector<TreeNode*> allPossibleFBT(int n)
    {
            if (n % 2 == 0)
                    return {};

            if (n == 1)
                    return { new TreeNode(0) };

            vector<TreeNode*> result;
            for (int i = 1; i < n; i += 2)
            {
                    int j = n - 1 - i;
                    vector<TreeNode*> left_tree = allPossibleFBT(i);
                    vector<TreeNode*> right_tree = allPossibleFBT(j);

                    for (auto left_node : left_tree)
                    {
                            for (auto right_node : right_tree)
                            {
                                    auto node = new TreeNode(0);
                                    node->left = left_node;
                                    node->right = right_node;
                                    result.push_back(node);
                            }
                    }
            }

            return result;
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690131900.A.462.html
※ 編輯: yam276 (123.193.249.242 臺灣), 07/24/2023 01:08:33
推 SecondRun: 大師