437. 路径总和 III

Posted on In , Views: Disqus:
LeetCode刷题系列。

描述

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

1
2
3
4
5
6
7
8
9
10

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

    1. 5 -> 3
    1. 5 -> 2 -> 1
    1. -3 -> 11

来源：力扣（LeetCode）
链接：437. Path Sum III

解题思路

总体的思路还是要递归，那么怎么递归呢？这是个问题。

一种比较简洁的思路是使用两个递归函数，其中一个递归函数sumUp是以当前节点为起点，其中参数有当前节点的指针* node，记录之前路径之和的变量pre，给定的路径和sum，返回和为sum的路径个数。

sumUp函数采用了前序遍历，对于每个遍历到的节点进行处理，用变量 pre 来记录之前路径之和，然后 cur 为 pre 加上当前节点值，如果 cur 等于 sum，那么返回结果时要加1，然后对当前节点的左右子节点调用递归函数求解。

另外一个递归函数就是原pathSum函数的递归调用，在 pathSum 函数中，我们对当前结点调用 sumUp 函数，加上对左右子结点调用 pathSum 递归函数，三者的返回值相加就是所求，具体代码见解法一。

另外一种仅采用一个递归函数，姑且叫做helper。其中参数有当前节点的指针* node，给定的路径和sum，路径和是否仅包含当前节点的值的标记flag，返回和为sum的路径总个数。

helper函数也是采用了前序遍历，用number表示需要返回的个数，当路径不仅仅包含当前节点及其左右子节点时，将后续递归函数当中的sum用sum减去当前节点的val来代替，即sum - node->val。具体代码见解法二。

然后再提交以后的查看详情里面看到有人用栈进行求解，这边给代码加下注释放在解法三，大家对照着看看。

显然，解法三洋洋洒洒要100多行，而且是在不包括测试代码的情况下，要是说此题简单我是不相信的(￣▽￣)

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int sumUp(struct TreeNode* node, int pre, int sum){
    if(!node) return 0;
    int cur = pre + node->val;
    return (cur == sum) + sumUp(node->left, cur, sum) + sumUp(node->right, cur, sum);
}


int pathSum(struct TreeNode* root, int sum){
    
    if(!root) return 0;
    return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}

解法二

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int helper(struct TreeNode* node, int sum, int flag){
    
    if (!node)
        return 0;
    else{
        int number = 0;
        if (node->val == sum){
            number += 1;
        }
        if (flag == 1){
            number += helper(node->left, sum, 1);
            number += helper(node->right, sum, 1);
        }
        
        number += helper(node->left, sum - node->val, 0);
        number += helper(node->right, sum - node->val, 0);
        
        return number;
    }
    
}

int pathSum(struct TreeNode* root, int sum){
    return helper(root, sum, 1);
}


解法三

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 声明最大节点数
#define MAX_CNT 1000

// 结构体声明
typedef struct{
    int target;                             // 路径和的数值
    int total;                              // 路径和等于给定数值target的路径总数
    int cnt;                                // 当前栈内节点指针的个数
    struct TreeNode * data[MAX_CNT + 1];    // 节点指针数组
}Stack;


//栈的初始化
void StackInit(Stack *st, int target, int total, int cnt){
    st->cnt = cnt;
    st->target = target;
    st->total = total;
}

// 压栈
void StackPush(Stack *st, struct TreeNode *node)
{ 
    if ((st->cnt < MAX_CNT) && (node != NULL)) {

        st->data[st->cnt++] = node;
    }
}

// 弹栈
struct TreeNode* StackPop(Stack *st)
{
    struct TreeNode *node = NULL;
    if (st->cnt > 0) {
        node = st->data[st->cnt--];
    }

    return node;
}

// 计算当前栈内节点满足target的路径个数，这个路径是逐个相加的
int CaclSumCorrect(Stack *st)
{
    int i = st->cnt;
    int sum = 0;
    int result = 0;
    

    for (; i > 0; --i) {
        sum += st->data[i - 1]->val;
        if (sum == st->target) {
            result += 1;
        }
    }    

    return result;
}

// 遍历并递归调用，并且以栈的指针为入场，调用是传地址，直接修改栈的相关参数
void VisitTree(struct TreeNode* root, Stack *st)
{
    int result;
    if (root != NULL) {
        //压栈
        StackPush(st, root);   
        //计算满足要求的路径总数
        st->total += CaclSumCorrect(st);
        //左递归
        if (root->left != NULL) {
            VisitTree(root->left, st);
        }
        //右递归
        if (root->right != NULL) {
            VisitTree(root->right, st);
        }
        
        //弹栈
        StackPop(st);
    } 
    
}

int pathSum(struct TreeNode* root, int sum){
    
    //声明栈，这里声明的不是栈的指针，后面在初始化的时候
    Stack st;
     
    //栈的初始化
    StackInit(&st, sum, 0, 0);
    
    //注意，这里第二个参数传的是st的地址
    VisitTree(root, &st);
    
    return st.total;
}

参考