[CareerCup] 4.9 All Paths Sum 所有路径和

简介:

4.9 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf.

这道题给我们一个二叉树,让我们找出所有的路径,其和为给定的值,而且说了路径不必起始于根,终止于叶节点,但必须是向下的一条路径。LeetCode中相似的题有Path Sum 二叉树的路径和 和 Path Sum II 二叉树路径之和之二。但是那题要找的是起始于根,终止于叶节点的路径,而这题是找出所有的路径。所以要稍稍复杂一些。这题的解题思路是先求出给定二叉树的深度,关于求二叉树的深度可以参见我之前的博客Maximum Depth of Binary Tree 二叉树的最大深度。然后我们建立一个大小为树的最大深度的一维向量,用来存每一层路径上的值。然后从第一层开始递归,对每一个节点,更新当前层的path,然后从此层向第一层遍历,将path各层值加起来,如果等于sum的话,就把这道路径打印或者保存起来,然后在对当前节点的左右子节点分别递归调用。时间复杂度为O(nlgn),空间复杂度为O(lgn),参见代码如下:

解法一:

class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        if (!root) return vector<vector<int> >();
        int depth = getDepth(root);
        vector<vector<int> > res;
        vector<int> path(depth, INT_MIN);
        pathSumDFS(root, sum, 0, path, res);
        return res;
    }
    void pathSumDFS(TreeNode *root, int sum, int level, vector<int> &path, vector<vector<int> > &res) {
        if (!root) return;
        path[level] = root->val;
        int t = 0;
        for (int i = level; i >= 0; i--) {
            t += path[i];
            if (t == sum) {
                savePath(path, i, level, res);
            }
        }
        pathSumDFS(root->left, sum, level + 1, path, res);
        pathSumDFS(root->right, sum, level + 1, path, res);
        path[level] = INT_MIN;
    }
    void savePath(vector<int> &path, int start, int end, vector<vector<int> > &res) {
        vector<int> out;
        for (int i = start; i <= end; ++i) {
            out.push_back(path[i]);
        }
        res.push_back(out);
    }
    int getDepth(TreeNode *root) {
        if (!root) return 0;
        return 1 + max(getDepth(root->left), getDepth(root->right));
    }
};

然而书上的解法并不是最简洁的,下面这种方法是评论区的网友提出来的,感觉很简洁很好,赞一个~

解法二:

class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        if (!root) return {};
        vector<vector<int>> res;
        vector<int> path;
        helper(root, sum, path, res);
        return res;
    }
    void helper(TreeNode* node, int sum, vector<int>& path, vector<vector<int>>& res) {
        if (!node) return;
        path.push_back(node->val);
        int curSum = 0;
        for (int i = path.size() - 1; i >= 0; --i) {
            curSum += path[i];
            if (curSum == sum) res.push_back(vector<int>(path.begin() + i, path.end()));
        }
        helper(node->left, sum, path, res);
        helper(node->right, sum, path, res);
        path.pop_back();
    }
};

本文转自博客园Grandyang的博客,原文链接:所有路径和[CareerCup] 4.9 All Paths Sum ,如需转载请自行联系原博主。

相关文章
|
2天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
8天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
7天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
7天前
|
云安全 人工智能 自然语言处理
阿里云x硅基流动:AI安全护栏助力构建可信模型生态
阿里云AI安全护栏:大模型的“智能过滤系统”。
|
8天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
631 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
|
10天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
754 2