首页 > 代码库 > leetcode 129. Sum Root to Leaf Numbers
leetcode 129. Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1 / 2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
1 int sumNumbers(TreeNode *root) 2 { 3 int total_sum = 0; 4 int path_sum = 0; 5 stack<TreeNode *> node_stack; 6 TreeNode *visit = root, *last_visit = NULL, *peek = NULL; 7 8 while (!node_stack.empty() || (visit != NULL)) 9 {10 if (visit != NULL)11 {12 path_sum = path_sum * 10 + visit->val;13 if ((visit->left == NULL) && (visit->right == NULL)) // leaf node14 {15 total_sum += path_sum;16 }17 node_stack.push(visit);18 visit = visit->left;19 }20 else21 {22 peek = node_stack.top();23 if (peek->right != NULL && peek->right != last_visit)24 {25 visit = peek->right;26 }27 else28 {29 node_stack.pop();30 last_visit = peek;31 path_sum /= 10;32 }33 }34 }35 36 return total_sum;37 }
leetcode 129. Sum Root to Leaf Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。