Day 23：二元树分支总和 sums of the branches

今天这题题目是国外论坛分享的面试题，
其实也是LeetCode-Path Sum的衍生题，直接来刷题吧！

简单复习一下二元树 Binary Tree 的特点：

1. 可以为空
2. 0 ≤ Node's Degree ≤ 2
3. 子树有左右方向之区分

还记得Day 19：二元树遍历 Binary Tree Traversal我们提到的三种追踪方式吗？
今天我们会用到
前序追踪（preOrder） “中左右”的方式还解决这题问题！

假设以下是我们一开始的树

先思考一下，如果我们要获得这棵树的所有树枝的加总，我们应该要怎麽做？
我们应该要拜访每一个节点（node）对吧？
那要用哪一种方式呢？depth-first-search-like？

我们拜访每一个节点的时候去把每个拜访过的节点的值加起来。
我们知道，在二元树的结构中，是有左右之分的，也就是每个节点都有可能有左右儿子。
这种重复性的结构我们应该想到用递回的方式。

没错我们其实就只用建立一个递回方法，把我们目前计算的结果存到array依序往左右儿子传递，直到左右儿子已经没有後代就停止计算。

就像下面这张图
在一开始初始化sum = 0
如第一次的答案 → 粉红色１的路径开始往下把拜访过的数加总到sum，
走访的路径像是

5 → 哇５的左手牵着4 → 还没完唷 4 的左手还拉着11 → 11左手又有 7 → 确定左边没了 → 回去11 发现右手还有9 在把暂存的+9 → 9没有左右手了 → 退回4 ....这样的走访路径

时间复杂度: O(n) 因为我们需要走访每个node 没个动作也只需要简单的加总
空间复杂度: O(n) 为什麽呢？我们可以简单说因为我们不可能获得超过n的branch

我们来深入了解一下为什麽？
在范例中我们可以观察到，答案的数量应该会跟完全没有左右小孩的节点一样多，在树中我们叫做叶子(leaf)。
这张图我们可以观察到：当二元树每一层都长满的时候，下一层的节点数都恰好会是上一层的两倍。
而所有的节点树恰好就是 2^n层 -1
而最後一层的节点树会是 2^ n-1
我们每次用来储存结果的list大概就是为後一层的节点树，也就是 2^ (n-1)
而节点的总数N = 2^n -1
所以 2^ (n-1) = (N+1) / 2
如果 N 趋近无限大时，我们可以说，最後一层的节点树就会大约是一半的总节点树。

可以参考下面来思考看看！

那我们来实作吧！

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function branchSums(root) {
  const sum = [];
  getBranchSums(root, 0, sum);
  return sum;
}

//递回function
function getBranchSums(node, tmpSum, sum) {
  //一开始检查是否为节点 不是就停止递回呼叫
  if (!node) return;
  const currentSum = tmpSum + node.value;
  //如果左右都没有节点了 答案放入sum
  if (!node.left && !node.right) {
    sum.push(currentSum);
    return;
  }

  //呼叫自己
  getBranchSums(node.left, currentSum, sum);
  getBranchSums(node.right, currentSum, sum);
}

明日题目预告：一起来实作min-heap吧！ Ｍin-Heap construction