[演算法題目] Node Depths

本題資訊

難度：easy
使用語言：C++
相關概念：Binary Tree

---

題目敘述

The distance between a node in a Binary Tree and the tree’s root is called the node’s depth. Write a function that takes in a Binary Tree and returns the sum of its nodes’ depths.
Each BinaryTree node has an integer value, a left child node, and a right child node. Children nodes can either be BinaryTree nodes themselves or None / null.

這題主要是計算在 Binary Tree 中所有的 node 深度加總，不過我想最主要的 Binary Tree 概念也要有。

建構一顆樹

這倒是沒什麼懸念，依照題目要求去打造一顆樹即可。

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value) {
    this->value = value;
    left = nullptr;
    right = nullptr;
  }
};

如何計算深度

在考慮怎麼加總比較有效率之前，應該要思考如何計算一個 node 的深度XD 首先大概可以從位置開始考慮？另外如果用遞迴的概念的話，可以使用「child node 的深度 = parent node 的深度 + 1」這個概念下手，一直推上去就可以知道指定 node 的深度了。

不過不知道是不是我對 tree 的實際操作沒那麼熟的關係，在剛開始看到此題時我覺得好像難度比平常的 easy 再上去一點點，但又不到 medium 就是了。

Idea 1

很純粹思考從 root 開始走訪各個 node，記得左邊右邊都要走訪，並在走訪後深度+1。
因為這題剛好是加總，所以可以直接寫在 return 表示加總的結果。

using namespace std;

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value) {
    this->value = value;
    left = nullptr;
    right = nullptr;
  }
};

int nodeDepths(BinaryTree *root, int depth = 0) {
  if (root == nullptr)
    return 0;
  return depth + nodeDepths(root->left, depth + 1) + nodeDepths(root->right, depth + 1);
}

時間複雜度（平均）：\(O(n)\)，\(n\) 是 Binary Tree 的 node 個數。
空間複雜度：\(O(h)\)，\(h\) 是 Binary Tree 的高度。

Idea 2

我個人覺得這個作法比較迷幻一點，利用 stack 的特性操作，原則上也是走訪一次深度就加上 1。

using namespace std;

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value) {
    this->value = value;
    left = nullptr;
    right = nullptr;
  }
};

struct Level {
  BinaryTree *root;
  int depth;
};

int nodeDepths(BinaryTree *root) {
  int sum = 0;
  vector<Level> stack = {{root, 0}};
  while (stack.size() > 0){
    BinaryTree *node = stack.back().root;
    int depth = stack.back().depth;
    stack.pop_back();
    
    if (node == nullptr) continue;

    sum += depth;
    stack.push_back(Level{node->left, depth + 1});
    stack.push_back(Level{node->right, depth + 1});
  }
  return sum;
}

時間複雜度（平均）：\(O(n)\)，\(n\) 是 Binary Tree 的 node 個數。
空間複雜度：\(O(h)\)，\(h\) 是 Binary Tree 的高度。