返回

[Leetcode]113. Path Sum II(C++)

题目描述

题目链接: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.

例子

Input: [5,4,8,11,null,13,4,7,2,null,null,5,1], sum = 22 Output: [ [5,4,11,2], [5,8,4,5] ]

Note

  • A leaf is a node with no children

解题思路

用 dfs 递归搜索子节点:

  • 如果当前节点为空,直接返回,否则将其值推入当前路径中,并将目标值减去当前节点值
  • 如果当前节点为叶节点
    • 如果更新后的目标值为 0,表示当前路径和为目标值,将当前路径推入结果中并返回
    • 否则直接返回
  • 对左右子树使用更新后的目标值进行搜索
  • 搜索完成后将当前路径中最后一个元素推出,以免影响其他路径

代码如下:

/**
 * 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) {}
 * };
 */

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> pathSum(TreeNode* root, int sum) {
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        search(root, sum, path, result);
        return result;
    }

private:
    void search(TreeNode* root, int target, std::vector<int>& path,
                std::vector<std::vector<int>>& result) {
        if (!root) return;
        path.push_back(root->val);
        target -= root->val;
        if (!root->left && !root->right) {
            if (target == 0) {
                result.push_back(path);
            }
        }
        search(root->left, target, path, result);
        search(root->right, target, path, result);

        path.pop_back();
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(h) – 递归深度

GitHub 代码同步地址: 113.PathSumIi.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy