[筆記] AlphaCamp 不只是刷題的 Leetcode 訓練營

章節連結

課程相關資訊
LeetCode 題目

894. All Possible Full Binary Trees

一腳踏入軟體工程師寫 Code 的世界，不免俗地會碰上 Leetcode 的測驗，來測試你的溝通力、系統性地解決問題的能力和如何化抽象為具體。第五週的活動主要為抽象的資料結構 Stacks, Queues & Tree 實作。因為份量較多，所以拆成兩篇來寫。

課程對應章節：Week5 U32~U39

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

LeetCode 題目

894. All Possible Full Binary Trees

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

var allPossibleFBT = function(N) {
    if(N % 2 === 0) return [] // 符合條件的 N 都為奇數
    if(N === 1) return [new TreeNode(0)] // 如果是 1 直接回傳 TreeNode(0)
    
    const trees = []
    // 以 root 為核心，分為左右兩半
    // 左邊可能的節點數 和 右邊可能的節點數，分別遞迴
    // 將左邊、右邊的樹，分別生成一個完整的 Tree 
    for(let i=1; i<= N-2; i+=2){
        const leftTrees = allPossibleFBT(i)
        const rightTrees = allPossibleFBT(N-i-1)
        
        for(let left of leftTrees){
            for(let right of rightTrees){
                const root =  new TreeNode(0, left, right)
                trees.push(root)
            }
        }
    }
    
    return trees
};