[Leetcode] Sum root to leaf numbers求根到叶节点的数字之和

Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path1->2->3which represents the number123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
/ \
2 3

The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.

Return the sum = 12 + 13 =25.

思路:每条root到叶节点的路径代表着一个数。沿着路径,各节点的值在数中由高位到低位,这个有点像在数组中,数组A[]的元素是0~9的整数,求由整个数组元素构成整数,方法是定义变量sum=0,然后sum=sum*10+A[i]。对应一条路径去看,也可以同样去做,只不过这里当前元素的值为当前节点所对应的值。对整棵二叉树,是左子树所有路径构成整数的和加上右子树。考虑到用递归(DFS)来解,遇到两种情况,一、如何处理节点:空节点、叶节点、一般节点;二、如何求和。

针对问题一,遇到空节点,说明其没有左右孩子了,而且对应的值为0;遇到一般节点,则由sum直接加上当前节点的值;遇到叶节点,说明递归到最底端了,本次的递归结束,返回sum,即递归条件构造好了;针对问题二,类似数组的问题,对整棵二叉树节点值得和

可以写为sum(左子树)+sum(右子树),则递归公式确定了。对于递归算法,我也是一知半解,打算通过做题来熟悉,欢迎大神支招!

 /**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sumNumbers(TreeNode *root)
{
int sum=;
return sumSubtree(root,sum);
} int sumSubtree(TreeNode *root,int sum)
{
if(root==NULL) return ; //不存在,则认为值为0
sum=sum*+root->val; if(root->left==NULL&&root->right==NULL) //到达叶节点
return sum; return sumSubtree(root->left,sum)+sumSubtree(root->right,sum);
}
};
上一篇:Netty学习一:基本知识


下一篇:[LeetCode] Sum Root to Leaf Numbers dfs,深度搜索