如何使用递归函数的返回值
257. Binary Tree Paths、二叉树的所有路径
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
代码语言:javascript复制输入:
1
/
2 3
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
代码语言:javascript复制class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if (root == NULL)
return res;
if (root->left == NULL && root->right == NULL) {
res.push_back( to_string(root->val));
return res;
}
vector<string> leftS = binaryTreePaths(root->left);
for (int i = 0; i < leftS.size(); i ) {
res.push_back( to_string(root->val) "->" leftS[i]);
}
vector<string> rightS = binaryTreePaths(root->right);
for (int i = 0; i < rightS.size(); i ) {
res.push_back( to_string(root->val) "->" rightS[i]);
}
return res;
}
};
113. Path Sum II
129. Sum Root to Leaf Numbers
437. 路径总和 III
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
代码语言:javascript复制root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/
5 -3
/
3 2 11
/
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
代码语言:javascript复制class Solution {
public:
int ans=0;
int pathSum(TreeNode* root, int sum) {
if(root){
dfs(root,sum);
pathSum(root->left,sum);
pathSum(root->right,sum);
}
return ans;
}
void dfs(TreeNode* root, int sum){
if(!root)return;
if(root->val==sum)ans ;
dfs(root->left,sum-root->val);
dfs(root->right,sum-root->val);
}
};
代码语言:javascript复制// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if ( root == NULL )
return 0;
int res = findPath( root, sum);
res = pathSum( root->left, sum);
res = pathSum( root->right, sum);
return res;
}
private:
// 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
// 返回这样的路径个数
int findPath( TreeNode* node, int num) {
if ( node == NULL)
return 0;
int res = 0;
if( node->val == num)
res = 1;
res = findPath(node->left, num - node->val);
res = findPath(node->right, num - node->val);
return res;
}
};
// @lc code=end