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; }};新聞熱點
疑難解答
