Leetcode — 894. All Possible Full Binary Trees (中文)

問題連結: https://leetcode.com/problems/all-possible-full-binary-trees/

Full binary tree的定義: 二元樹中的每個節點都只有0或2個子節點

給定n節點, 回傳所有包含n節點的full binary trees, 回傳形式須把所有可能的樹的根結點裝進List中

⚠️各節點 node 的值皆為 0, 回傳的list裡面樹的順序可隨意

範例:
Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
->我們總共有五個不同的Full Binary Tree, 如下圖 -

N = 7 (Photo credit to Leetcode.)

想法:

讓我們先來把N還小的前三個case畫下來, 來看我們可不可以找到答案的規律:

Example Full Binary Tree (part 1)

(因為當 n=2, 4, 或任何偶數節點數的時候, 我們無法組成一個full binary tree, 因此前三小的cases才會是n=1, 3, 5)

從上述的圖, 我們可以發現當節點數為1或3的時候, 我們只有一種可能的樹, 但當節點數為5的時候, 我們可以看到根節點的左子樹和右子樹其實就是我們節點數為1或3的時候組成的樹

因此, 我們也可以利用上面圖中的所有樹, 來找節點數為7的所有5個full binary tree組合, 如下圖所示:

⚠️為了圖的清楚度, 我們把節點數為5所可以建的兩個樹用代碼5a和5b來表示

Example Full Binary Tree (part 2)

因此, 我們可以下結論說, 當我們想要組一個節點數為n的full binary tree的時候, 我們需要先知道怎麼組節點數為n-2, n-4, … 等的full binary tree

現在問題似乎沒有那麼難了, 只要我們可以找到如何組所有節點數為n-2的樹, 我們就可以得出所有組成節點數為n的樹組合

程式邏輯:

根據上面我們得出的結論, 其實用遞迴來解這題會最容易, 因為我們這題就會被要求設計一個回傳所有 給定節點數n組成的full binary tree, 代表如果我們可以用遞迴的方式呼叫自己, 我們也可以找到n-2, n-4 等的所有樹組合, 也就是我們也同時找到了所有組左子樹跟右子樹的可能組合

我們會需要用一個迴圈來控制我們這輪的時候 左子樹和右子樹的節點數, 因為我們每次都需製造總節點數為n的樹, 因此左子樹和右子數的總節點數應該永遠保持n-1, 扣掉的那個1則是要留給 負責把左右子樹連在一起的根結點

每次我們呼叫allPossibleFBT(i)的時候, 代表我們已經找到 用i個節點組成的full binary tree的所有可能了, 因此這些也都將會是我們潛在的左子樹的根結點 - 也就是我們最終答案的根節點的左節點; 當我們呼叫allPossibleFBT(n-i)的時候也是相同意思, 我們也找到了所有潛在的右節點了
▶️因此, 我們會再用迴圈來走訪所有潛在的左右節點, 並且每次都創一個新的根節點把其中一個左節點跟其中一個右節點綁在一起, 直到我們試過每個左右節點配合的組合

以下為 5ms 的程式碼, 贏過 23% —

public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> rst = new ArrayList<>();
        if(n==1)
            rst.add(new TreeNode(0));
        n-=1;//root
        for(int i=1;i<=n;i+=2)
        {
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(n-i);
            for(TreeNode l: left)
            {
                for(TreeNode r: right)
                {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    rst.add(root);
                }
            }
        }
        
        return rst;
    }

而在上述程式碼, 我們很高的機率都把時間浪費在 為某幾個特定節點數重複找所有的樹, 因此當我們為某個節點數找到所有可能的樹的時候, 我們都把結果存在map裡面, 這樣我們下次有需要找這個節點數的結果的時候, 就不用重複跑一整個一模一樣的流程了

以下為1ms 的程式碼, 贏過 99% —

public List<TreeNode> allPossibleFBT(int n) {
        return helper(n, new HashMap<>());
    }
    public List<TreeNode> helper(int n, Map<Integer, List<TreeNode> > map){
        List<TreeNode> rst = map.get(n);
        if(rst!=null)
            return rst;
        rst = new ArrayList<>();
        if(n==1)
            rst.add(new TreeNode(0));
        n-=1;//root 
        for(int i=1;i<=n;i+=2)
        {
            List<TreeNode> left = helper(i, map);
            List<TreeNode> right = helper(n-i, map);
            for(TreeNode l: left)
            {
                for(TreeNode r: right)
                {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    rst.add(root);
                }
            }
        }
        map.put(n+1, rst);
        return rst;
    }