Path Sum II
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]]
分析: dfs求解即可
/**
* 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:
void find(TreeNode* root, int sum,vector<int>& curPath, vector<vector<int>> & res ){
if(root==nullptr)
return;
if(root->left){
curPath.push_back(root->left->val);
find(root->left, sum-root->val, curPath,res);
curPath.pop_back();
}
if(root->right){
curPath.push_back(root->right->val);
find(root->right, sum-root->val,curPath,res);
curPath.pop_back();
}
if(root->left==nullptr && root->right==nullptr && sum==root->val)
res.push_back(curPath); return;
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
if(root==nullptr)
return res;
vector<int> curPath;
curPath.push_back(root->val);
find(root, sum, curPath, res); return res;
}
};
Path Sum II的更多相关文章
-
Leetcode 笔记 113 - Path Sum II
题目链接:Path Sum II | LeetCode OJ Given a binary tree and a sum, find all root-to-leaf paths where each ...
-
[leetcode]Path Sum II
Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals ...
-
【leetcode】Path Sum II
Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals ...
-
32. Path Sum &;&; Path Sum II
Path Sum OJ: https://oj.leetcode.com/problems/path-sum/ Given a binary tree and a sum, determine if ...
-
LeetCode: Path Sum II 解题报告
Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals ...
-
[LeetCode#110, 112, 113]Balanced Binary Tree, Path Sum, Path Sum II
Problem 1 [Balanced Binary Tree] Given a binary tree, determine if it is height-balanced. For this p ...
-
Path Sum,Path Sum II
Path Sum Total Accepted: 81706 Total Submissions: 269391 Difficulty: Easy Given a binary tree and a ...
-
LeetCode之“树”:Path Sum &;&; Path Sum II
Path Sum 题目链接 题目要求: Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc ...
-
leetcode 112. Path Sum 、 113. Path Sum II 、437. Path Sum III
112. Path Sum 自己的一个错误写法: class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if(root ...
随机推荐
-
Html 制作相册
本文主要讲述采用Html5+jQuery+CSS 制作相册的小小记录. 主要功能点: Html5进行布局 调用jQuery(借用官网的一句话:The Write Less, Do More)极大的简化 ...
-
spring整合httpclient
<beans xmlns="http://www.springframework.org/schema/beans" xmlns:context="http://w ...
-
android 制作自定义标题栏
1.在AndroidManifest.xml设置主题 android:theme="@android:style/Theme.NoTitleBar.Fullscreen" 2.在l ...
-
mybatis 自动生成xml文件配置
http://blog.csdn.net/techbirds_bao/article/details/9233599/
-
vim插件:显示树形目录插件NERDTree安装 和 使用
下载和配置 NERDTree插件的官方地址如下,可以从这里获取最新的版本 https://github.com/scrooloose/nerdtree 下载zip安装包 或者使用下面官网源文件安装方法 ...
-
span设置宽和高当没有内容的时候也可撑开
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...
-
PHP的几种排序算法的比较
这里列出了几种PHP的排序算法的时间比较的结果,,希望对大家有所帮助 /* * php 四种排序算法的时间与内置的sort排序比较 * 3000个元素,四种算法的排序所用的时间比较 * 冒泡排序 85 ...
-
记录一些基本的git命令
本地操作 向git仓库添加文件 git status 查看工作区文件状态 git add a.php 将文件添加到暂存区 git commit -m "描述" 将文 ...
-
s21day20 python笔记
s21day20 python笔记 一.内容回顾 面向对象的三大特性 封装 函数封装到类 数据封装到对象 继承 多态 二.成员 2.1 类成员 类变量(静态字段) 定义:写在类的下一级,和方法同一级 ...
-
Linux系统IO分析工具之iotstat常用参数介绍
Linux系统IO分析工具之iotstat常用参数介绍 作者:尹正杰 版权声明:原创作品,谢绝转载!否则将追究法律责任. 1>.安装iostat [root@flume115 ~]# yum - ...