[AcWing]47. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

保证树中结点值均不小于 0。

数据范围

树中结点的数量 [0,1000]。

样例

1
2
3
4
5
6
7
8
9
10
给出二叉树如下所示，并给出num=22。
      5
     / \
    4   6
   /   / \
  12  13  6
 /  \    / \
9    1  5   1

输出：[[5,4,12,1],[5,6,6,5]]

算法思路

DFS的过程中，在遇到叶子节点的时候进行累加求和，并且提交path作为ans之一。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 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;
    
    // 节点，当前累计的值，目标值
    void dfs(TreeNode * root, int sum, int target){
        // 遇到叶子节点下面的空节点，或者是棵空树，什么也不做，反正返回的是ans
        if(!root) return;
        // 将当前遇到节点加入路径集合
        path.push_back(root -> val);
        // 进行累加计算
        sum += root -> val;
        
        // 有左子树就开始递归左子树
        if(root -> left) dfs(root -> left, sum, target);
        // 有右子树就开始递归右子树
        if(root -> right) dfs(root -> right, sum, target);
        // 剩下的情况就是，左子树和右子树都没有，说明是当前节点是叶子节点
        // 订正：不一定是左子树和右子树都没有，或许它是只有一个子树，因此不能无脑开始计算并且提交答案
        // 确定是叶子节点才能计算并且提交答案
        if(!root -> left && !root -> right){
            if(sum == target) ans.push_back(path);
        }
        
        // 不成功也不管了，反正最终会提交一个ans
        
        // 每次dfs都需要恢复现场
        path.pop_back();
    }
    
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        // 从根节点找到每个分支的叶子节点
        dfs(root, 0, sum);
        return ans;
    }
};

注意事项：

1
2
3
path.push_back(root -> val);

path.pop_back();// 恢复现场

在DFS过程中，上面这两行到底怎么理解？

DFS的过程中，可以用函数调用栈来表示。如果调用四次DFS，则有四个DFS压入栈中，path也会有四个节点的值。在DFS出栈的过程中，如果不恢复现场，则会出现函数调用栈空了，但path的里面值依旧没有减少。

归根结底，四次DFS，path会加入四个节点的值，通过path.pop_back()会清除掉这四个节点的值。这样能够保证DFS在结束一个分支，再次开启新的分支的时候path是干净的。

时间复杂度分析

  • 最坏时间复杂度O(n<sup>2</sup>)：在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。路径的数目为O(n)，并且每一条路径的节点个数也为 O(n)。要想将n个路径的所有节点都统计起来，需要的时间复杂度是O(n<sup>2</sup>)。
  • 平均时间复杂度O(n)：由于每个节点最多只会被访问一次，所以时间复杂度是O(n)。

但是注意：在大多数情况下，二叉树不会退化成链表，因此大部分情况下的时间复杂度都是线性的。

我认为时间复杂度还是能看做O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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;

    void dfs(TreeNode * root, int target){
        if(!root) return;
                
        path.push_back(root -> val);
        
        // 只有到叶子结点的时候才开始全部计算
        if(!root -> left && !root -> right){

            int total = 0;
            for(int i = 0; i < path.size(); i++){
                total += path[i];
            }
            if(total == target){
                // 提交答案
                ans.push_back(path);
            }
        }
        
        if(root -> left) dfs(root -> left, target);
        if(root -> right) dfs(root -> right, target);
        
        // 恢复现场
        path.pop_back();
    }

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

我的算法。