Leetcode解题: Path Sum II (113)

发表于 | 分类于

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

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

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

解法1： DFS

关于求所有的路径之类的题目，首先想到的都是DFS。 这道题也不例外。 用DFS遍历tree， 每一次往下一个node， 就把当前的sum减去node的val， 如果碰到叶子并且叶子的val和所剩的val相等，则加入paths中。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int> > paths;
        vector<int> path;
        helper(root, sum, path, paths);
        return paths;  
    }
private:
    void helper(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
        if (!node) {
            return;
        }
        path.push_back(node->val);
        if (!node->left && !node->right && sum == node->val) {
            paths.push_back(path);
        }
        helper(node->left, sum - node->val, path, paths);
        helper(node->right, sum - node->val, path, paths);
        
        path.pop_back();
    }
};

Java

1