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 3The 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.
s思路： 1. 树的问题，根本就是遍历。这道题一看肯定不能用bfs，因为要找到从root到leaf的数就需要dfs来找，遍历顺序是首先根，再左，后右，故：pre-order. 2. 要求和，则需要一个变量来表示这个最后的和；同时还需要一个变量表示目前从root到leaf的数。
//方法1：recursive来做，简单。class Solution {public: void helper(TreeNode* root,int cur,int&sum){ if(!root) return; cur=cur*10+root->val;//根 if(!root->left&&!root->right){ sum+=cur; return; } helper(root->left,cur,sum);//左 helper(root->right,cur,sum);//右 } int sumNumbers(TreeNode* root) { // int sum=0; helper(root,0,sum); return sum; }};//方法2：iterative:pre-order，stack，两个指针pre,pnow.class Solution {public: int sumNumbers(TreeNode* root) { stack<TreeNode*> ss; TreeNode* pnow=root,*pre=NULL; int sum=0,cur=0; while(pnow||!ss.empty()){ while(pnow){ cur=cur*10+pnow->val; ss.push(pnow); pnow=pnow->left; } pnow=ss.top(); if(!pnow->left&&!pnow->right) sum+=cur; if(pnow->right&&pnow->right!=pre){ pnow=pnow->right; }else{ pre=pnow; cur/=10; pnow=NULL; ss.pop(); } } return sum; }};新闻热点
疑难解答
