Description
給定一個 binary tree 的 root，回傳最深點的值之總和。此題限定節點的數量介於 $[1, 10^4]$，且節點的值介於 $[1, 100]$。
Example 1:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Example 2:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19Solution
本題有兩種解法，第一，可以利用 for loop 每層迭代，當迭代到樹的最底部時將所有的節點總和再回傳，這種方式的優點為速度較快，避開函式呼叫造成的 cost。第二，可以利用 recursive 以及 depth first search 的方式先將樹的深度求出，再利用另一個 recursive 將符合深度的節點找出並加起來，利用 recursive 可以使程式碼看起來精簡易讀，且測試發現使用到的記憶體較少，但是因為有多層的函式呼叫，導致速度較慢。
Solution 1 – for loop
我們可以利用兩個 vector<TreeNode*> 容器 nodes 、tmp達成我們的目標，其中 nodes 用來記錄目前相同層之節點指標，tmp 則是紀錄下一層之節點指標。若發現 tmp 不為空代表可能還有更深層的節點，因此將 tmp 內容移動至 nodes 裡面，並將 tmp 清空再一次進行同樣的動作。若 tmp 裡面是空的，代表當前的 nodes 裡面的節點已經達到最深層，我們可以將 nodes 裡的節點總和後即為答案。
Solution 2 – recursion
這個方法可以拆為兩步驟。首先我們可以利用 recursive 的方式搜尋此樹最深的層數，以下逐步說明如何建立 recursive 函式。假設我們有一個函式 $f(\text{node})$ 可以幫助我們計算出以 $\text{node}$ 為 root 的 binary tree 會有幾層。我們可以很直接的推導出以下式子:$$
f(\text{node}) = \max \bigg\{f(\text{node’s left}), f(\text{node’s right}) \bigg\} + 1
$$ 當前 $\text{node}$ 的深度等於左右兩個 child 中深度較深的那個加上 $1$。我們可以將 $f(\text{node’s left})$ 以及 $f(\text{node’s right})$ 一直用同樣的方式展開，直到我們展開到某一個最深節點之子節點，我們統稱 $\text{null}$，我們可以很直覺地將此點深度設為零 $f(\text{null}) = 0$，藉此回推至最初節點 $\text{node}$ 之深度。至此我們已將 DFS 的架構敘述完畢，若尚未了解透徹，可以利用下圖幫助理解。
取得最深層數後，我們可以利用另一個 recursive 函式幫助我們計算出最深層節點之總和，以下逐步說明如何建立此 recursive 函式。假設我們有另一個函式 $g(\text{node}; \text{depth}, \text{maxDepth})$ 可以算出 $\text{node}$ 以下之最深節點之總和，需要注意的是可能此節點以下並沒有連接到任何最深的節點，要判斷有沒有最深節點必須附帶兩個額外的參數，$\text{depth}$ 以及 $\text{maxDepth}$，分別記錄當前層的深度以及 binary tree 的深度。我們可以推導出以下等式：$$
\begin{aligned}
g(\text{node}; \text{depth}, &\text{maxDepth}) = \\
&g(\text{node’s right}; \text{depth + 1}, \text{maxDepth}) + \\
&g(\text{node’s left}; \text{depth + 1}, \text{maxDepth})
\end{aligned}
$$ 當前 $\text{node}$ 以下的最深節點和，等於左右子節點以下的最深節點和之和。我們一邊往下層展開，一邊紀錄每層節點之深度，當展開到最底部的節點時，我們可以比較 $\text{depth}$ 和 $\text{maxDepth}$ 這兩個變數的差異，若是該節點沒有達到最深則我們返回 $0$，代表我們不計入該節點的值，若是該節點深度等於最深之深度時返回該節點的值，計入最後的總和中。可以參考以下圖例幫助理解。
完整程式碼如下：
// Solution 1 - for loop
class Solution {
public:
int deepestLeavesSum(TreeNode* root) {
vector<TreeNode*> nodes = {root};
vector<TreeNode*> tmp = {};
int ans = 0;
while (true)
{
for (auto &node: nodes)
{
if (node->right != nullptr) tmp.push_back(node->right);
if (node->left != nullptr) tmp.push_back(node->left);
}
if (tmp.size() == 0)
{
for (auto &node: nodes)
{
ans += node->val;
}
break;
}
nodes = move(tmp);
}
return ans;
}
};
// Solution 2 - recursion
class Solution {
public:
int deepestLeavesSum(TreeNode* root) {
int maxDepth = find_max_depth(root, 1);
return deepestLeavesSum(root, 1, maxDepth);
}
int find_max_depth(TreeNode *node, int depth)
{
if (!node) return 0;
return max(
find_max_depth(node->right, depth + 1),
find_max_depth(node->left, depth + 1)) + 1;
}
int deepestLeavesSum(TreeNode *node, int depth, int &maxDepth)
{
if (!node) return 0;
else if (depth == maxDepth) return node->val;
return deepestLeavesSum(node->right, depth + 1, maxDepth) + \
deepestLeavesSum(node->left, depth + 1, maxDepth);
}
};