leetcode437：路径总和III

题目链接

leetcode

题目描述

给定一个二叉树的根节点 root 和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

C++ 代码

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 二叉树结点的定义
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) {}
};

const int NULL_NODE = -1001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    深度优先搜索：穷举所有可能，访问每一个结点，检测以该结点为起始结点且向下的路径有多少种。
    递归遍历每一个结点所有可能的路径，然后将这些路径数目相加作为结果。
    递归函数定义：返回以结点 p 为起点向下且满足路径总和为 val 的路径数目。

    时间复杂度：O(n^2)
        其中 n 为该二叉树结点的个数。
        对于每一个结点，需要遍历以该结点为根结点的子树的所有结点，
        对每个结点都求一次以该结点为起点的路径数目，因此时间复杂度为 O(n^2)。
    空间复杂度：O(n)
        递归需要在栈上开辟空间。
*/
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return 0;

        // long long res = dfs(root, targetSum);
        int res = dfs(root, targetSum);
        res += pathSum(root->left, targetSum);
        res += pathSum(root->right, targetSum);
        return res;
    }

    int dfs(TreeNode* node, long targetSum) {
        if (node == nullptr) return 0;

        long res = 0;
        if (node->val == targetSum) res ++;
        res += dfs(node->left, targetSum - node->val);
        res += dfs(node->right, targetSum - node->val);

        return res;
    }
};

/*
    前缀和

    结点前缀和的定义：由根结点到当前结点的路径上所有结点的和。
    先序遍历二叉树，记录根结点 root 到当前结点 p 的路径上除当前结点以外所有结点的前缀和，
    在已保存的路径前缀和中查找，是否存在等于当前结点到根结点的前缀和（cur - targetSum）。
    
    时间复杂度：O(n)
        其中 n 为二叉树中结点的个数。利用前缀和只需遍历一次二叉树。
    空间复杂度：O(n)

    参考链接：
        https://www.acwing.com/solution/content/56049/
*/
class Solution_1 {
public:
    int pathSum(TreeNode* root, int targetSum) {
        sum2cnt[0] = 1; // 初始化
        return dfs(root, targetSum, 0);
    }

    int dfs(TreeNode* root, int targetSum, long curSum) {
        if (root == nullptr) return 0;

        int res = 0;
        curSum += root->val;
        if (sum2cnt.count(curSum - targetSum)) {
            res = sum2cnt[curSum - targetSum];
        }
        sum2cnt[curSum] ++;
        res += dfs(root->left, targetSum, curSum);
        res += dfs(root->right, targetSum, curSum);
        sum2cnt[curSum] --;

        return res;
    }

private:
    unordered_map<long, int> sum2cnt;
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {10, 5, -3, 3, 2, NULL_NODE, 11, 3, -2, NULL_NODE, 1};
    // 目标和
    int sum = 8;

    // 创建二叉树
    TreeNode* root = createTree(nums);
    levelOrderTraversal(root);

    // 找出所有路径总和等于目标和的所有路径的数量
    int res = solution.pathSum(root, sum);
    // 打印结果
    cout << "Number of paths with sum " << sum << ": " << res << endl;

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package main

import (
	"fmt"
)

// 定义二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// createTree 创建二叉树（层序遍历输入）
func createTree(values []int) *TreeNode {
	if len(values) == 0 || values[0] == -1 {
		return nil
	}

	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1

	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		// 左子节点
		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		// 右子节点
		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}

	return root
}

/*
    基本思路：
        前缀和：
            使用前缀和的思想，记录从根节点到当前节点的路径和。
            如果当前路径和减去目标值的结果在前缀和计数器中存在，则说明存在一条满足条件的路径。
        深度优先搜索 (DFS)：
            使用递归遍历二叉树，同时维护当前路径和和前缀和计数器。
            在递归返回时，需要回溯，恢复前缀和计数器的状态。
        计数器：
            使用一个哈希表（map）记录前缀和的出现次数，
            初始时 prefixSumCount[0] = 1，表示路径和为 0 的情况。

    时间复杂度：O(n)
        DFS 遍历：每个节点只访问一次，时间复杂度为 O(n)，其中 n 是树中节点的数量。
        每次访问节点时，哈希表操作（查找和更新）的时间复杂度为 O(1)。
    空间复杂度：O(n)
        递归调用栈：递归调用的深度为树的高度，最坏情况下为 O(n)，最好情况下为 O(logn)。
        哈希表：哈希表存储前缀和的出现次数，空间复杂度为 O(n)。
*/
// pathSum 计算路径和等于目标值的路径数量
func pathSum(root *TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}

	// 前缀和计数器
	prefixSumCount := make(map[int]int)
	prefixSumCount[0] = 1

	var dfs func(node *TreeNode, currentSum int) int
	dfs = func(node *TreeNode, currentSum int) int {
		if node == nil {
			return 0
		}

        currentSum += node.Val
        count := prefixSumCount[currentSum - targetSum]

		// 更新前缀和计数器
		prefixSumCount[currentSum] ++
		count += dfs(node.Left, currentSum) + dfs(node.Right, currentSum)
		// 回溯，恢复前缀和计数器
		prefixSumCount[currentSum] --

		return count
	}

	return dfs(root, 0)
}

func main() {
	// 测试用例
	testCases := []struct {
		values     []int
		targetSum  int
		expected   int
	}{
		{
			values:    []int{10,5,-3,3,2,-1,11,3,-2,-1,1},
			targetSum: 8,
			expected:  3,
		},
		{
			values:    []int{5,4,8,11,-1,13,4,7,2,-1,-1,5,1},
			targetSum: 22,
			expected:  3,
		},
	}

	for i, tc := range testCases {
		root := createTree(tc.values)
		fmt.Printf("Test Case %d, Input: values = %v, targetSum = %d\n", i+1, tc.values, tc.targetSum)
		result := pathSum(root, tc.targetSum)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}
#leetcode
leetcode437：路径总和III
https://lcf163.github.io/2024/05/19/leetcode437：路径总和III/
作者
乘风的小站
发布于
2024年5月19日
许可协议