aboutsummaryrefslogtreecommitdiff
path: root/sum_root_leaf_num.cpp
blob: d1bc9c6a5d378cbc3d74aa3967833500400b1478 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 129. Sum Root to Leaf Numbers
#include "leetcode.h"

/*
 * given 'root' of binary tree containing digits 0-9 only. each root-to-leaf
 * pattern in the tree represents a number. eg. root-to-leaf path 1->2->3
 * represents the integer 123. return total sum of all root-to-leaf numbers.
 * test cases will fit in 32-bit integer. a leaf node is a node with no children
 */

class Solution {
public:
  int sumNumbers(TreeNode *root) {
    int sum = 0, curr = 0, depth = 0;
    while (root) {
      if (root->left) {
        auto pre = root->left;
        depth = 1;
        while (pre->right && pre->right != root) {
          pre = pre->right;
          depth++;
        }
        if (!pre->right) {
          pre->right = root;
          curr = curr * 10 + root->val;
          root = root->left;
        } else {
          pre->right = nullptr;
          if (!pre->left)
            sum += curr;
          curr /= pow(10, depth);
        }
      } else {
        curr = curr * 10 + root->val;
        if (!root->right)
          sum += curr;
        root = root->right;
      }
    }
    return sum;
  }
};