首页 > 学院 > 开发设计 > 正文

Leetcode 129. Sum Root to Leaf Numbers

2019-11-14 09:40:51
字体:
来源:转载
供稿:网友

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.

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; }};
上一篇:表单

下一篇:linux内核目录结构

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表