====
1302, Deepest leaves sum
====
tree
DFS, BFS
====
DFS:
1. 題目給一個TreeNode
從(root, 0//lvl, depth)開始DFS
2. 懶人法, vec<int>sum[i] 紀錄每i層depth的total
在DFS中
如果sum size等於傳入的lvl, 則表示這層depth第一次加入到sum, 所以sum.push_back
否則, 表示已經有index 'lvl', 加入到sum[lvl]
//初始root 0, sum size也零, sum.push_back == sum[0]
//root右子樹 1, sum size卻是2, 表示有左子樹加入過了, 合併到sum[lvl] == sum[1]
3. 最終return vector最後一個元素 == sum.back
----
class Solution {
public:
vec<int> sum
int deepestLeaveSum(TreeNode* root){
dfs(root, 0)
return sum.back()
}
void dfs(TreeNode* node, int lvl){
if(sum.size() == lvl)
sum.push_back(node->val)
else
sum[lvl] += node->val
if(node->left) dfs(node->left, lvl+1)
if(node->right) dfs(node->right, lvl+1)
}
}
====
BFS:
1. 題目給一個TreeNode
依照lvl/depth加入queue, pop all並加總
2. 懶人法, 當queue不等於空
把sum清空
並且元素pop all並加總//for, 這樣就會得到每一層的sum
如果還有左子右子, push到queue
如果queue空, 表示最後一層leave做完了, return當次/最終sum
----
class Solution {
public:
int sum
int deepestLeaveSum(TreeNode* root) {
queue<TreeNode*> q
q.push(root)
while(!q.empty()){
sum=0
int qlen = q.size()
for(int i=0, i<qlen, i++) {
TreeNode* node = q.front()
q.pop()
sum+=node->val
if(node->left) q.push(node->left)
if(node->right) q.push(node->right)
}//for qlen
}//while q.empty
return sum
}
}
