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

598 0 0

作者:王大咩的图书馆

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（右子树），则递归公式确定了。对于递归算法，我也是一知半解，打算通过做题来熟悉，欢迎大神支招！

 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     {
14         int sum=0;
15         return sumSubtree(root,sum);    
16     }
17 
18     int sumSubtree(TreeNode *root,int sum)
19     {
20         if(root==NULL)  return 0;   //不存在，则认为值为0
21         sum=sum*10+root->val;
22 
23         if(root->left==NULL&&root->right==NULL) //到达叶节点
24             return sum;
25         
26         return sumSubtree(root->left,sum)+sumSubtree(root->right,sum);
27     }
28 };

内容来源于网络如有侵权请私信删除

标签：算法数据结构 LeetCode

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

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