【剑指offer】面试题25：二叉树中和为某一值的路径
2024-03-29 00:33:35
题目：
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路：
dfs一下就可以了。一般dfs肯定递归写比较方便。
注意，递归的结束条件是遇到叶节点，而不是遇到空指针。（如果是遇到空指针，则叶节点相当于判断了两次，然而写出来的代码出现了段错误，不知道为什么）
相关：树求和（里面好像dfs用循环写的~）
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int> > res;
if(root==NULL) return res; vector<TreeNode*> vec;
vec.push_back(root);
dfs(root,,expectNumber,vec,res); return res;
}
private:
void dfs(TreeNode* root,int sum,int expectNumber,vector<TreeNode*> &vec,vector<vector<int> > &res)
{
if(root->left==NULL && root->right==NULL)//递归结束条件应该是叶节点；而不是root==NULL
{
if((sum+root->val)==expectNumber)
{
vector<int> intvec;
for(int i=;i<vec.size();++i)
intvec.push_back(vec[i]->val);
res.push_back(intvec);//vector的该成员函数是以复制的方式加入
}
}
else
{
if(root->left)
{
vec.push_back(root->left);
dfs(root->left,sum+root->val,expectNumber,vec,res);//因为直接以sum+root->val参数传入的，所以后面不用恢复sum
vec.pop_back();
} if(root->right)
{
vec.push_back(root->right);
dfs(root->right,sum+root->val,expectNumber,vec,res);
vec.pop_back();
}
}
}
};
递归结束条件是空指针时的代码（有段错误）
提交时间：-- :: 语言：C++ 状态：段错误
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int> > res;
if(root==NULL) return res; vector<TreeNode*> vec;
vec.push_back(root);
dfs(root,,expectNumber,vec,res); return res;
}
private:
void dfs(TreeNode* root,int sum,int expectNumber,vector<TreeNode*> vec,vector<vector<int> > &res)
{
if(root==NULL)
{
if(sum==expectNumber)
{
vector<int> intvec;
for(int i=;i<vec.size();++i)
intvec.push_back(vec[i]->val);
res.push_back(intvec);//vector的该成员函数是以复制的方式加入
}
}
else
{
vec.push_back(root->left);
dfs(root->left,sum+root->val,expectNumber,vec,res);//因为直接以sum+root->val参数传入的，所以后面不用恢复sum
vec.pop_back(); vec.push_back(root->right);
dfs(root->right,sum+root->val,expectNumber,vec,res);
vec.pop_back();
}
}
};
最新文章
- 浅谈Service层为何要有接口
- Python~切片Slice
- django xadmin 模板的定制
- GitHub简历
- mysql优化(1) 观察服务器周期性变化
- IOS 数据库管理系统(SQLite)
- 1.Java为什么能跨平台运行？请简述原理
- JavaScript Array 对象方法 以及 如何区分javascript中的toString()、toLocaleString()、valueOf()方法
- 在被vue组件引用的 js 文件里获取组件实例this
- 分布式服务框架介绍：最成熟的开源NIO框架Netty
- 请求http页面的相关过程
- DBDocumentGenerator使用
- Kali学习笔记35：使用VBScript、PowerShell、DEBUG传输文件
- Codeforces Round #486 (Div. 3)-C. Equal Sums
- rsyncd的配置和使用
- 第一章 JS基础
- Object对象的浅拷贝与深拷贝方法详解
- ubuntu 14.04安装mysql数据库
- selenium设置代理，基于chrome浏览器
- Oracle OCI操作UDT相关学习