leetcode37:path-sum-ii
2024-08-27 10:57:02
题目描述
给定一个二叉树和一个值sum,请找出所有的根节点到叶子节点的节点值之和等于sum的路径,
例如:
给出如下的二叉树,sum=22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
例如:
给出如下的二叉树,sum=22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回
[
[5,4,11,2],
[5,8,4,5]
]
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 andsum = 22,
返回
[
[5,4,11,2],
[5,8,4,5]
]
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 andsum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
示例2
输出
[[1,2]]
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @param sum int整型
* @return int整型vector<vector<>>
*/
vector<vector<int> > pathSum(TreeNode* root, int sum) {
// write code here
vector <vector <int>> vv;
vector <int> v;
pathSum_Aux(root,sum,v,vv);
return vv;
}
void pathSum_Aux(TreeNode *root,int sum,vector <int> v,vector<vector<int>>&vv){
if (root==NULL)
return ;
v.push_back(root->val);
if (root->left ==NULL && root->right==NULL &&sum -root->val==0){
vv.push_back(v);
}
pathSum_Aux(root->left, sum-root->val, v,vv);
pathSum_Aux(root->right,sum-root->val,v,vv);
}
};
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
vector <vector<int>>res;
void dfspath(TreeNode *root,int num,vector<int>v){
if (!root)return ;
v.push_back(root->val);
if (root->left ==nullptr && root->right==nullptr){
if (num==root->val )res.push_back(v);
}
dfspath(root->left,num-root->val,v);
dfspath(root->right,num-root->val,v);
}
public:
/**
*
* @param root TreeNode类
* @param sum int整型
* @return int整型vector<vector<>>
*/
vector<vector<int> > pathSum(TreeNode* root, int sum) {
// write code here
vector <int>v;
dfspath(root, sum, v);
return res;
}
};
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param root TreeNode类
# @param sum int整型
# @return int整型二维数组
#
class Solution:
def pathSum(self , root , sum ):
# write code here
if not root:
return []
res=[]
def helper(root,remain,temp=[]):
temp_=temp+[root.val]
remain_=remain-root.val
if remain_==0 and not root.left and not root.right:
res.append(temp_)
return
if root.left:
helper(root.left,remain_,temp_)
if root.right:
helper(root.right,remain_,temp_)
helper(root,sum)
return res
最新文章
- javaWeb https连接器
- python 中的 try/except/else/finally语句
- nginx rewrite 实现二级域名跳转
- lesson32 Shopping for food
- POJ 2796 Feel Good(单调栈)
- iOS UILocalNotification 每2周,每两个月提醒
- 转载 从最简单的vector中sort用法到自定义比较函数comp后对结构体排序的sort算法
- C# WinForm获取当前路径汇总
- 再战map
- 深入浅出MongoDB(二)概述
- SRF之数据字典
- @jsonignore的作用
- 分布式PostGIS系列【2】——pgpool-II
- session与cookie的区别,有哪些不同之处
- [Locked] Flip Game I &; II
- 微信开发-微信JSSDK错误:invalid url domain
- 什么是语义化的HTML?为什么要做到语义化?
- jQuery之animate中的queue
- vue-cli项目开发/生产环境代理实现跨域请求+webpack配置开发/生产环境的接口地址
- 阿里云RDS备份在本地mysql快速还原
热门文章
- JavaScript按钮排他思想
- 【记】《.net之美》之读书笔记(二) C#中的泛型
- 用<; 100行代码向EPUB或Web服务器添加视频回放
- Java虚拟机诊断利器
- vue 下载jquery 下载layui-layer 下载vue-router
- <;二分查找+双指针+前缀和>;解决子数组和排序后的区间和
- zookeeper 集群搭建 转
- MySQL字段添加注释,但不改变字段的类型
- C# Webservice中如何实现方法重载--(方法名同名时出现的问题)
- 简述BIO到NIO的过程