首页 > 代码库 > LeetCode: Sum Root to Leaf Numbers
LeetCode: Sum Root to Leaf Numbers
LeetCode: 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.
地址：https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
算法：用递归的方法完成的。首先分别计算左右子树的和，并且把子树中所有叶子节点的深度记录下来，然后根的和=左子树的和+右子树的和+根的值*pow10（叶子节点的深度）。代码：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 int sumNumbers(TreeNode *root) {13 vector<int> level;14 if(!root) return 0;15 return sum(root,level);16 }17 int sum(TreeNode *root, vector<int> &level){18 if(!root) return -1;19 if(!root->left && !root->right){20 level.push_back(1);21 return root->val;22 }23 vector<int> left;24 int left_sum = sum(root->left,left);25 vector<int> right;26 int right_sum = sum(root->right,right);27 int total_sum = 0;28 if(left_sum >= 0){29 total_sum += left_sum;30 vector<int>::iterator it = left.begin();31 for(; it != left.end(); ++it){32 total_sum += (root->val * int(pow10(*it)));33 level.push_back(*it + 1);34 }35 }36 if(right_sum >= 0){37 total_sum += right_sum;38 vector<int>::iterator it = right.begin();39 for(; it != right.end(); ++it){40 total_sum += (root->val * int(pow10(*it)));41 level.push_back(*it + 1);42 }43 }44 return total_sum;45 }46 };
LeetCode: Sum Root to Leaf Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。