注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex129 Sum Root to Leaf Numbers  

2015-05-14 21:07:56|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
没什么难度,直接递归。

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.

话说我现在写递归还是有点儿水平了。

int traverse(struct TreeNode*current,int tempSum)
{
tempSum *= 10;
tempSum += current->val;

int value1, value2;
if (current->left == NULL&&current->right ==NULL)
{
return tempSum;
// 到达了叶子节点
}
{
if (current->right == NULL)
{
value1 = traverse(current->left, tempSum);
return value1;
}
else
{
if (current->left == NULL)
{
value2 = traverse(current->right, tempSum);
return value2;
}
else
{
value1 = traverse(current->left, tempSum);
value2 = traverse(current->right, tempSum);
int value = value1 + value2;
return value;
}
}

}
}

int sumNumbers(struct TreeNode* root) {
int sum = 0;
if (root == NULL)
return 0;
sum = traverse(root,sum);
printf("%d \n",sum);
return sum;
}



second time代码精简

class Solution {
public:
/*
* 这一题貌似用bfs不太好做
*/
int result;
int sumNumbers(TreeNode* root) {
result = 0;
if (root == NULL) return result;
int sum = 0;
dfs(root,sum);
return result;
}
void dfs(TreeNode* current,int sum)
{
if (current->left == NULL &&current->right ==NULL) result += sum*10+current->val;
else
{
if (current->left!=NULL) dfs(current->left,sum*10+current->val);
if (current->right!=NULL) dfs(current->right, sum*10 + current->val);
}
}
};

update 2015/12/2 更新一下java版本加上 bfs遍历

public class SumRoottoLeafNumbers {
private int result = 0;
public int sumNumbers(TreeNode root) {
return helper(root);
}
private int helper(TreeNode root) {
if (root == null) {
return result;
}
//dfs(root, 0);
//return result;
return bfs(root);
}
private void dfs(TreeNode root, int sum) {
if (root.left == null && root.right == null) {
// 到达叶子节点
result += sum * 10 + root.val;
} else {
int res = sum * 10 + root.val;
if (root.left != null) {
dfs(root.left, res);
}
if (root.right != null) {
dfs(root.right, res);
}
}
}
private int bfs(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> treeQueue = new LinkedList<>();
LinkedList<Integer> resQueue = new LinkedList<>();
treeQueue.add(root);
resQueue.add(root.val);
int count = 1;
int depth = 0;

int res = 0;

TreeNode current = null;
int num = 0;
while (!treeQueue.isEmpty()) {
current = treeQueue.peek();
treeQueue.pop();
count--;
num = resQueue.peek();
resQueue.pop();
if (current.left == null && current.right == null) {
res += num;
} else {
if (current.left != null) {
treeQueue.add(current.left);
resQueue.add(num * 10 + current.left.val);
}
if (current.right != null) {
treeQueue.add(current.right);
resQueue.add(num * 10 + current.right.val);
}
}
if (count == 0) {
count = treeQueue.size();
depth++;
}
}
return res;
}
}


  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017