diff options
Diffstat (limited to 'other/sum_root_leaf_num.cpp')
-rw-r--r-- | other/sum_root_leaf_num.cpp | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/other/sum_root_leaf_num.cpp b/other/sum_root_leaf_num.cpp new file mode 100644 index 0000000..d1bc9c6 --- /dev/null +++ b/other/sum_root_leaf_num.cpp @@ -0,0 +1,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; + } +}; |