二叉树中和为某一值的路径(C++中等区)

    科技2025-05-21  40

    二叉树中和为某一值的路径

    题目:输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

    示例: 给定如下二叉树,以及目标和 sum = 22, 返回: 提示: 节点总数 <= 10000


    解题思路

    采用前序遍历 + 递归回溯来解题 先序遍历: 按照 “根、左、右” 的顺序,遍历树的所有节点。 路径记录: 在先序遍历中,记录从根节点到当前节点的路径。当从根节点到叶节点形成的路径各节点值的和等于目标值 sum 时,将此路径加入结果容器中。

    算法流程:

    初始化: 结果列表 res ,路径列表 tem。pathSum(root, sum) 函数: 调用recursion(root, sum) 函数 返回值: 返回 res 即可。recursion(root, sum) 函数: 递推参数: 当前节点 root ,当前目标值 sum 。 终止条件: 若节点 root 为空,则直接返回。 递推工作: 路径更新: 将当前节点值 root->val 加入路径 tem ; 目标值更新: sum -= root->val(即目标值 sum 从 sum 减至 0 ); 路径记录: 当从根节点到叶节点形成的路径各节点值的和等于目标值 sum 时,将此路径加入结果容器中。 先序遍历: 递归左 / 右子节点。 路径恢复: 向上回溯前,需要将当前节点从路径 tem 中删除,即执行 tem.pop_back() 。

    链接:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/mian-shi-ti-34-er-cha-shu-zhong-he-wei-mou-yi-zh-5/


    代码展示

    代码如下:

    class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { if(!root) return {}; recursion(root,sum); return res; } void recursion(TreeNode* root,int sum) { if(!root) return; tem.push_back(root->val); sum-=root->val; //若sum为0且到达叶子节点则将一维数组插入到二维数组中 if(sum==0 && !root->left && !root->right) { res.push_back(tem); } //否则继续搜寻左子树 recursion(root->left,sum); //继续搜寻右子树 recursion(root->right,sum); //删除当期节点,便于回溯 tem.pop_back(); } private: vector<vector<int>> res; vector<int> tem; }; 执行用时:12 ms, 在所有 C++ 提交中击败了88.07%的用户 内存消耗:19.4 MB, 在所有 C++ 提交中击败了97.54%的用户
    Processed: 0.011, SQL: 8