diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/sum_root_leaf_num.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
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; + } +}; |