1302, Deepest leaves sum

====

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

  }

}