aboutsummaryrefslogtreecommitdiff
path: root/other/sum_root_leaf_num.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/sum_root_leaf_num.cpp')
-rw-r--r--other/sum_root_leaf_num.cpp42
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;
+ }
+};