1
// Itrative
2
class Solution {
3
 public:
4
  int sumRootToLeaf(TreeNode *root) {
5
    int sum = 0;
6
    stack<pair<TreeNode *, int>> s;
7
    s.push({root, 0});
8
    while (!s.empty()) {
9
      TreeNode *p = s.top().first;
10
      int num = s.top().second;
11
      s.pop();
12
      num = (num << 1) | p->val;
13
      if (p->left == NULL && p->right == NULL) sum += num;
14
      if (p->right) s.push({p->right, num});
15
      if (p->left) s.push({p->left, num});
16
    }
17
    return sum;
18
  }
19
};
20

21
// Recursive
22
class Solution {
23
  int sum = 0;
24

25
 public:
26
  void preorder(TreeNode *root, int num) {
27
    if (root == NULL) return;
28
    num = (num << 1) | root->val;
29
    if (root->left == NULL && root->right == NULL) sum += num;
30
    preorder(root->left, num);
31
    preorder(root->right, num);
32
  }
33
  int sumRootToLeaf(TreeNode *root) {
34
    preorder(root, 0);
35
    return sum;
36
  }
37
};