Path Sum
AC Rate: 872/2770
My Submissions
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:Given the below binary tree and
sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2
which sum is 22.
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool hasPathSum(TreeNode *root, int sum) { if (root == NULL) return false; if (root->left == NULL && root->right == NULL ) { if (root->val == sum) return true; else return false; } return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } };
Path Sum II
AC Rate: 691/2584
My Submissions
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] ]
/** * Definition for binary tree * 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) { vector<vector<int> > res; if (root == NULL) return res; vector<int> v; gen(res, v, root, 0, sum); return res; } void gen(vector<vector<int> >& res, vector<int>& v, TreeNode* cur, int s, int sum) { v.push_back(cur->val); if (cur->left == NULL && cur->right == NULL) { if (s+cur->val == sum) res.push_back(v); } else { if (cur->left != NULL) gen(res, v, cur->left, s + cur->val, sum); if (cur->right!= NULL) gen(res, v, cur->right,s + cur->val, sum); } v.pop_back(); } };
相关推荐
java java_leetcode题解之Path Sum III.java
public int PathSum(TreeNode root, int sum) { _count = 0; _sum = sum; Travel(root, new List()); return _count; } private void Travel(TreeNode current, List<int> ret) { if (current == null) { ...
java java_leetcode-112-path-sum
java java_leetcode-113-path-sumII
LeetCode — Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need...
python python_leetcode题解之112_Path_Sum
python python_leetcode题解之113_Path_Sum_II
javascript js_leetcode题解之112-path-sum.js
javascript js_leetcode题解之113-path-sum-ii.js
javascript js_leetcode题解之64-minimum-path-sum.js
c语言入门 C语言_leetcode题解之64-minimum-path-sum.c
python python_leetcode题解之124_Binary_Tree_Maximum_Path_Sum
javascript js_leetcode题解之124-binary-tree-maximum-path-sum.js
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
113. 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. Note: A leaf is a node with no children. Example: Given the below binary tree...
此外,文档还提到了另一个问题——路径总和II(Path Sum II),这是一个寻找二叉树中特定和的路径的问题。虽然没有给出完整的代码,但可以看出这个问题涉及到递归或深度优先搜索(DFS)的策略,可能需要使用回溯法来...
- **Path Sum II**:寻找所有从根节点到叶节点的路径,其路径和等于给定的目标值。 - **Flatten Binary Tree to Linked List**:将二叉树展平为单链表。 - **Validate Binary Search Tree**:验证一个二叉树是否...
31. Binary Tree Maximum Path Sum:二叉树中的最大路径和。 32. Binary Tree Upside Down:将一个二叉树进行翻转。 【位操作】 33. Single Number:找出数组中唯一不出现一次的数字。 34. Single Number II:找出...
再如,"Binary Tree Maximum Path Sum"问题,要求找到二叉树中从根节点到叶子节点的最大路径和。这个问题可以通过深度优先搜索或广度优先搜索结合动态规划来解决。 GuaZiDou的解决方案不仅包含了代码实现,通常还...