接續幾天會討論 Tree, Graph, DAG 與 topological。
今天討論的主題用 DFS/BFS 是 Tree，而 Tree 就是沒有 Cycle 的 Graph。

102. Binary Tree Level Order Traversal (medium)

題目敘述: 給一個二元樹的根節點，傳回其節點值的層序遍歷。

輸入輸出範例:

	   3
	 /  \
    9      20
          /  \
         15   7
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

我解題想法1 :用遞迴 DFS 方式寫的，在參數裡存好層數。

用 DFS 看輸入輸出範例 順序將會是:

3 -左-> 9 -左-> NULL
        -右-> NULL (返回到3)
  -右-> 20 -左-> 15
         -右-> 7  (結束)

(3, 9, 20, 15, 7)

獻上程式碼:

class Solution {
public:
    vector<vector<int>> res;
    void dfs(TreeNode * root, int level) {
        if (!root) return;
        if(res.size() < level+1) {
            res.push_back({root->val});
        }else{
            res[level].push_back(root->val);
        }
        dfs(root->left, level+1);
        dfs(root->right, level+1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        dfs(root, 0);
        return res;
    }
};

想法2 : 迭代的 BFS 走訪 Tree
題目的範例:

	   3
	 /  \
    9      20
          /  \
         15   7

BFS 走訪順序 3, 9, 20, 15, 7

我解題想法是將走訪最終結果想成是 [3, 9, 20, 15, 7] 一維結果。在 while 迴圈內的每次迭代都是走訪一個節點(非整層)，因此我需要用三個整數去記錄走訪 Tree 的狀態: levelPtr (這層最後節點的位數), nextLevelPtr (下層最後節點的位數), currPtr (已遍歷的節點數量)， (currPtr <= levelPtr <= nextLevelPtr) ，當遍歷完一層時 (if (levelPtr == currPtr))，將該層的節點們存入 res。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode *> qu;
        qu.push(root);
        int levelPtr = 1, nextLevelPtr = 1, currPtr = 0;
        vector<int> tmp;

        while (!qu.empty()) {
            currPtr += 1;
            TreeNode* node = qu.front();
            qu.pop();
            tmp.push_back(node->val);
            if (node->left) {
                nextLevelPtr++;
                qu.push(node->left);
            }
            if (node->right) {
                nextLevelPtr++;
                qu.push(node->right);
            }
            if (levelPtr == currPtr) {
                res.push_back(tmp);
                tmp.clear();
                levelPtr = nextLevelPtr;
            }
        }
        return res;
    }
};

此題檢討:
看了 討論區的解答 與教授的解法 (兩者類似)，發現 while 內的每次迭代是將該層的節點存進一個 vector 後，先記錄當層的節點數 (int s = qu.size();) ，此層的所有節點會被加入到一個臨時 vector 中。這樣的寫法讓整個程式碼變得更加簡潔

時間複雜度 O(n)，走訪整棵 BFS tree。

1161. Maximum Level Sum of a Binary Tree (medium)

講解題目: 為每層的節點值算總和，返回最大總和的層數 (1-index)
跟 102. Binary Tree Level Order Traversal 題目很像，以下程式碼是根據之前 BFS 的檢討寫出來的結果。

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        int maxLevel , currLevel = 0, maxSum = INT_MIN;
        queue<TreeNode *> qu;
        qu.push(root);
        while (!qu.empty()) {
            int quSize = qu.size(), currSum = 0;
            currLevel += 1;
            for (int i = 0; i < quSize; i++) {
                TreeNode *node = qu.front();
                currSum += node->val;
                qu.pop();
                if(node->left) qu.push(node->left);
                if(node->right) qu.push(node->right);
            }
            if (maxSum < currSum) {
                maxSum = currSum;
                maxLevel = currLevel;
            }
        }
        return maxLevel;
    }
};

時間複雜度同樣 O(n)

以上是我的解題紀錄，由於我的太生疏了，因此寫出來的程式碼還有很多的進步空間!

這幾天發現，將自己與他人的程式碼進行對比分析，能夠幫助我更加清晰地理解解題思路，這種自言自語式的分析就像是「黃色小鴨除錯法」啊！