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

HT·生活

123

 
 
 

日志

 
 

ex113 Path Sum II  

2015-05-19 22:57:03|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
深度优先遍历,求root->leaf的路径和等于给定值的path

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]
直接深度优先递归就行了,没有特别的难度。见c代码

int traverse(struct TreeNode* current, int** result, int *returnSize, int** columnSizes, int*trace, int sum, int depth, int target)
{
// result用于存储最后的输出结果 returnSize记录result的维数

// trace 是记录当前key值, depth表示当前深度,维护trace的下标
// sum是指定的路径和
if ((current->left == NULL) && (current->right == NULL))
{
trace[depth] = current->val;
sum += current->val;
if (sum == target)
{
// 找到路径了
columnSizes[0][returnSize[0]] = depth + 1;
result[returnSize[0]] = (int*)malloc((depth + 1)*sizeof(int));
memcpy(result[returnSize[0]], trace, (depth + 1)*sizeof(int));
returnSize[0]++;
}
return depth;
}
else
{
int left = 0, right = 0;
trace[depth] = current->val;
sum += current->val;
if (current->left != NULL)
{
left = traverse(current->left, result, returnSize, columnSizes, trace, sum, depth + 1, target);
}

if (current->right != NULL)
{
right = traverse(current->right, result, returnSize, columnSizes, trace, sum, depth + 1, target);
}

return left>right ? left : right; //其实返回值没有多大用
}
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** pathSum(struct TreeNode* root, int sum, int** columnSizes, int* returnSize) {

if (root == NULL)
return NULL;
int maxHeight = 10000; //最大高度设大一点儿,不然oj不让过
int *trace = NULL;
trace = (int*)malloc(maxHeight*sizeof(int));

//columnSizes = (int**)malloc(1*sizeof(int*)); //只分配一个文件就够了
columnSizes[0] = (int*)malloc(maxHeight*sizeof(int));


int maxTimes = 10000; //出现的次数开始的时候也开大一点儿
int **result = (int**)malloc(maxTimes * sizeof(int*)); // sum == target 假设最多等于100次
returnSize[0] = 0;

int depth = 0;

int target = sum;
traverse(root, result, returnSize, columnSizes, trace, 0, depth, target);
return result;
}

second time 精简代码,bfs和dfs重写,这个题其实和word ladder很相似的,如果用bfs做的话

class Solution {
public:
vector<vector<int>> result;
vector<vector<int>> pathSum(TreeNode* root, int sum){
if (!root) return result;
//vector<int>tmp;
//dfs(root,sum,0,tmp);
bfs(root,sum);
return result;
}
void bfs(TreeNode* root, int target)
{
//使用宽度优先遍历,需要加一个队列记录当前节点的和
//bfs

TreeNode*current = NULL;
queue<TreeNode*>myQueue;
queue<int>sum;
myQueue.push(root);
sum.push(root->val);

map<TreeNode*, TreeNode*> prePath; //store the prefix for rebuilding the path
vector<TreeNode*> res; //store the "right" nodes
int currentSum;
while (!myQueue.empty())
{
current = myQueue.front();
currentSum = sum.front();

if (currentSum == target&&!current->left&&!current->right) res.push_back(current);
myQueue.pop();
sum.pop();
if (current->left != NULL)
{
myQueue.push(current->left);
sum.push(currentSum + current->left->val);
prePath[current->left] = current;
}
if (current->right != NULL)
{
myQueue.push(current->right);
sum.push(currentSum + current->right->val);
prePath[current->right] = current;
}
}
// rebuild the path
vector<int>tmp;
for (int i = 0; i < res.size(); i++)
{
current = res[i];
tmp.clear();
while (current!=root)
{
tmp.push_back(current->val);
current = prePath[current];
}
tmp.push_back(root->val);
reverse(tmp.begin(),tmp.end());
result.push_back(tmp);
}
}
void dfs(TreeNode* root, int target, int current,vector<int>res)
{
//深度优先很简洁
//very neat
res.push_back(root->val);
if (!root->left &&!root->right)
if (current + root->val == target) result.push_back(res);
else res.pop_back();
else
{
if (root->left) dfs(root->left, target, current + root->val, res);
if (root->right) dfs(root->right, target, current + root->val, res);
res.pop_back();
}

}
};

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

历史上的今天

评论

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

页脚

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