《Cracking the Coding Interview》——第4章：树和图——题目9
2024-09-28 00:58:39
2014-03-19 05:07
题目：给定一棵二叉树T和一个值value，在T中找出所有加起来和等于value的路径。路径的起点和终点都可以是树的任意节点。
解法：我偷了个懒，直接把这棵树看成一个无向图，用DFS来进行暴力搜索解决问题。因为没有什么数据顺序或是范围的限制，所以搜索剪枝好像也不太容易。
代码：
// 4.9 Find all paths in a binary tree, the path doesn't have to start or end at the root or a leaf node.
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right; TreeNode(int _val = ):val(_val), left(nullptr), right(nullptr) {};
}; void constructTree(TreeNode *&root)
{
int val; scanf("%d", &val);
if (val == ) {
root = nullptr;
} else {
root = new TreeNode(val);
constructTree(root->left);
constructTree(root->right);
}
} void constructGraph(TreeNode *root, unordered_map<TreeNode *, unordered_set<TreeNode *> > &graph)
{
if (root->left != nullptr) {
graph[root].insert(root->left);
graph[root->left].insert(root);
constructGraph(root->left, graph);
} if (root->right != nullptr) {
graph[root].insert(root->right);
graph[root->right].insert(root);
constructGraph(root->right, graph);
}
} void DFS(TreeNode *node, vector<TreeNode *> &path, int sum, const int target,
unordered_set<TreeNode *> &checked,
unordered_map<TreeNode *, unordered_set<TreeNode *> > &graph, vector<vector<TreeNode *> > &result)
{
path.push_back(node);
checked.insert(node); if (sum == target) {
result.push_back(path);
}
unordered_set<TreeNode *>::iterator it;
for (it = graph[node].begin(); it != graph[node].end(); ++it) {
if (checked.find(*it) == checked.end()) {
DFS(*it, path, sum + (*it)->val, target, checked, graph, result);
}
} checked.erase(node);
path.pop_back();
} void doDFS(TreeNode *root, vector<TreeNode *> &path, const int target,
unordered_set<TreeNode *> &checked,
unordered_map<TreeNode *, unordered_set<TreeNode *> > &graph, vector<vector<TreeNode *> > &result)
{
path.clear();
checked.clear();
DFS(root, path, root->val, target, checked, graph, result);
if (root->left != nullptr) {
doDFS(root->left, path, target, checked, graph, result);
}
if (root->right != nullptr) {
doDFS(root->right, path, target, checked, graph, result);
}
} void clearTree(TreeNode *&root)
{
if (root == nullptr) {
return;
} if (root->left != nullptr) {
clearTree(root->left);
}
if (root->right != nullptr) {
clearTree(root->right);
}
delete root;
root = nullptr;
} int main()
{
int i, j;
int target;
TreeNode *root;
unordered_map<TreeNode *, unordered_set<TreeNode *> > graph;
unordered_map<TreeNode *, unordered_set<TreeNode *> >::iterator it;
unordered_set<TreeNode *> checked;
vector<TreeNode *> path;
vector<vector<TreeNode *> > result; while (true) {
constructTree(root);
if (root == nullptr) {
break;
}
constructGraph(root, graph);
while (scanf("%d", &target) == && target) {
doDFS(root, path, target, checked, graph, result);
if (result.empty()) {
printf("No path is found.\n");
} else {
for (i = ; i < (int)result.size(); ++i) {
printf("%d", result[i][]->val);
for (j = ; j < (int)result[i].size(); ++j) {
printf("->%d", result[i][j]->val);
}
result[i].clear();
printf("\n");
}
result.clear();
}
path.clear();
checked.clear();
}
for (it = graph.begin(); it != graph.end(); ++it) {
(it->second).clear();
}
graph.clear();
clearTree(root);
} return ;
}
最新文章
- C# Mvc异常处理过滤器
- TComboBoxEx和 TComboBox
- Pathoto项目：AWS+golang+beego搭建
- C# “快捷方式” 实现程序开机启动
- 【Python】 Django 怎么实现 联合主键？
- 查看Linux磁盘空间大小
- hdu 4679 Terrorist’s destroy 树形DP
- Java容器详解
- [WF4.0 实战] WPF + WCF + WF 打造Hello World（基础篇）
- JUnit4测试出错（一）
- Highcharts tooltip显示多条线的信息
- requirejs、vue、vuex、vue-route的结合使用，您认为可行吗？
- Tomcat8源码笔记(六)连接器Connector分析
- AspNet Core2 浏览器缓存使用
- 关于jvm钩子 Runtime.getRuntime().addShutdownHook
- UTF-8编码占几个字节?
- 禁用xampp的ssl功能
- Net Core SignalR 测试，可以用于unity、Layair、白鹭引擎、大数据分析平台等高可用消息实时通信器。
- 005PHP文件处理——目录操作，统计大小 filesize unlink
- Python 基础 模块