[leetcode] Path sum路径之和

简介:
要求
给定树,与路径和,判断是否存在从跟到叶子之和为给定值的路径。比如下图中,给定路径之和为22,存在路径<5,4,11,2>,因此返回true;否则返回false.
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 5
思路
递归,从跟到叶子判断,如果在叶子处剩下的给定值恰好为给定值,那么返回ture.
参考代码
复制代码
/**
 * 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;
        else if (root != NULL && root->left == NULL && root->right == NULL)
        {
            if (sum == root->val)
                return true;
            else
                return false;
        }
        else
            return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }
};
复制代码

 

扩展

求出所有符合条件的路径。例如,上题中返回<<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:
    void addPath(TreeNode *root, int sum, vector<int> tmp, vector<vector<int> > &rev)
    {
        if (root != NULL && root->left == NULL && root->right == NULL && root->val == sum)
        {
            tmp.push_back(root->val);
            rev.push_back(tmp);
            tmp.pop_back();
        }
        if (root->left != NULL)
        {
            tmp.push_back(root->val);
            addPath(root->left, sum - root->val, tmp, rev);
            tmp.pop_back();
        }
        if (root->right != NULL)
        {
            tmp.push_back(root->val);
            addPath(root->right, sum - root->val, tmp, rev);
            tmp.pop_back();
        }
    }
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> > rev;
        if (root == NULL)
            return rev;
    
        vector<int> tmp;

        addPath(root, sum, tmp, rev);
        return rev;
    }
};
复制代码

 

 

 



本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/p/3710308.html,如需转载请自行联系原作者

相关文章
|
1月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
23 0
|
1月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
28 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
12 0
|
3月前
|
存储 算法 Linux
LeetCode第71题简化路径
文章讲述了LeetCode第71题"简化路径"的解题方法,利用栈的数据结构特性来处理路径中的"."和"..",实现路径的简化。
LeetCode第71题简化路径
|
3月前
|
算法
LeetCode第64题最小路径和
LeetCode第64题"最小路径和"的解题方法,运用动态规划思想,通过构建一个dp数组来记录到达每个点的最小路径和,从而高效求解。
LeetCode第64题最小路径和
|
3月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
41 4
|
3月前
|
存储 Python
【Leetcode刷题Python】滑雪路径消耗时间:Testing Round #16 (Unrated) C. Skier
Leetcode题目"Testing Round #16 (Unrated) C. Skier"的Python解决方案,题目要求计算给定滑雪路径字符串的总耗时,其中未走过的边耗时5秒,走过的边耗时1秒。
50 4
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
56 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2