LeetCode Path Sum II (DFS)
2024-10-17 22:03:56
题意:
给一棵二叉树,每个叶子到根的路径之和为sum的,将所有可能的路径装进vector返回。
思路:
节点的值可能为负的。这样子就必须到了叶节点才能判断,而不能中途进行剪枝。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/ class Solution {
public:
vector<vector<int> > pathSum(TreeNode* root, int sum) {
if(root==NULL) return ans;
DFS(root,,sum,tmp);
return ans;
}
void DFS(TreeNode* t,int n,const int& sum,vector<int>& num)
{
num.push_back(t->val);
n+=t->val; if(t->left==NULL&&t->right==NULL)
{
if(n==sum) ans.push_back(num);
}
else
{
if(t->left) DFS(t->left,n,sum,num);
if(t->right) DFS(t->right,n,sum,num);
}
num.pop_back();
}
private:
vector<vector<int>> ans;
vector<int> tmp;
};
AC代码
最新文章
- 浅谈display:flex
- 政府应急平台之GIS一张图-flex/java
- 怎么清除file控件的文件路径
- 正确配置Linux系统ulimit值的方法【转】
- 小鸟哥哥博客 For SAE
- ICPC-CAMP day1 D.Around the world
- Linux中/usr与/var目录详解
- Centos 卸载OpenJdk
- 七周七语言——Prolog(二)
- tomcat中开启的对SSL(https)的支持
- iOS开发:创建真机调试证书 分类: ios相关 2015-04-10 10:22 149人阅读 评论(0) 收藏
- BZOJ 1019 :[SHOI2008]汉诺塔(递推)
- Kotlin初探
- java web 之 listen 与 filter
- VS 2017 开发安卓环境搭建 问题总结
- Android Studio精彩案例(一)《ActionBar和 ViewPager版仿网易新闻客户端》
- js数据结构与算法——集合
- maven手动安装jar包到本地仓库,以ojdbc6为例
- 【BZOJ5292】[BJOI2018]治疗之雨(高斯消元)
- Zephyr的Time、Timer、sleep