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
.
自己刚开始的想法是:先定义一个结构体,这个结构体里面除了定义左右节点,以及这个数的值以外,同时定义这个节点的高度,同时记录这个节点所能包含的叶节点的个数。
这样,通过递归的方法,先求出每个节点的高度,和包含的叶节点的个数,然后接下来,遍历每个节点,这个节点乘以他的高度乘以10,再乘以所包含的叶节点的个数,相加即可。
实际上,求高度的过程完全是可以避免的:以前总是以为,只有知道了我要乘以10,乘以100还是1000之后,我才能去乘,然后去求值。实际上,用递归完全可以避免这个问题。
这一层乘以10,然后递归。下一层次如果还有,自然就会乘以100了。以此类推。
这样,递归即可解决这个问题。
下面的是别人的代码:
Anwser 1:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void calSum(TreeNode *root, int val, int &sum){ if(root == NULL){ return; } if(root->left == NULL && root->right == NULL){ sum += root->val + val * 10; return; } calSum(root->left, val * 10 + root->val, sum); calSum(root->right, val * 10 + root->val, sum); } int sumNumbers(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function int sum = 0; calSum(root, 0, sum); return sum; } };
原文链接: https://www.cnblogs.com/kamendula/archive/2013/05/03/3058395.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/86976
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!