// 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; } };