Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
給你一棵二元樹和一個總和值,找到從樹根到樹葉的路徑中,所有節點加總等於給予的總和值的路徑。
提示:一個樹葉就是沒有小孩的節點。
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 DFS(vector<vector<int>>& ans, vector<int> path, TreeNode* node, int sum, int target)
{
if(!node)
{
return;
}
path.push_back(node->val);
sum+=node->val;
if(!node->left && !node->right)
{
if(sum == target)
ans.push_back(path);
return;
}
DFS(ans,path,node->left,sum,target);
DFS(ans,path,node->right,sum,target);
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> ans;
DFS(ans,vector<int>(0,0),root,0,sum);
return ans;
}
};
LeetCode
C++
1. Two Sum
Nov 15, 2023You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:
Nov 15, 2023Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 109 + 7.
Nov 9, 2023There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network.
Nov 9, 2023or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up