题目描述

给定一棵二叉树和一个 $sum$，在从根节点到叶节点的路径中，找到和等于 $sum$ 的所有路径。

注意：叶节点指没有儿子的节点。

样例

给定如下二叉树以及 $sum = 22$：

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

返回：

[
   [5,4,11,2],
   [5,8,4,5]
]

算法

(递归) $O(n^2)$

这道题目和 Path Sum 基本一样，不同点在于需要把所有路径记录下来。

递归，自顶向下从根节点往叶节点走，每走过一个节点，就让 $sum$ 减去该节点的值，则如果走到某个叶节点时，$sum$ 恰好为0，则说明从根节点到这个叶节点的路径上的数的和等于 $sum$，此时需要把这条路径记录下来。

时间复杂度分析：除了记录路径这部分，每个节点仅被遍历一次，且维护 $sum$ 和路径的复杂度都是 $O(1)$，所以时间复杂度是 $O(n)$；而记录路径这部分：n个节点的二叉树的叶子节点数最多是 $O(n)$ 级别的，且路径的长度最多也是 $O(n)$ 级别的，所以时间复杂度最坏是 $O(n^2)$。且最坏情况可以达到：假设总共有 $n$ 个节点，用 $n/2$ 个节点从根节点开始建一条很长的链，然后用剩下 $n/2$ 个节点建一课完全二叉树接在链的结尾。则此时叶节点个数是 $(n/2 + 1) / 2 \sim O(n)$，所有路径的长度均是 $n/2 + log(n/2 + 1) \sim O(n)$。所以总时间复杂度是 $O(n^2)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> pathSum(TreeNode* root, int sum)
    {
        if (!root) return ans;
        dfs(root, sum);
        return ans;
    }

    void dfs(TreeNode* root, int sum)
    { 
        path.push_back(root->val);
        sum -= root->val;
        if (root->left || root->right)
        {
            if (root->left) dfs(root->left, sum);
            if (root->right) dfs(root->right, sum);
        }
        else
        {
            if (!sum)
            {
                ans.push_back(path);
            }
        }
        path.pop_back();
    }
};