力扣练习——44 路径总和 III

  10

 /  \

5   -3
1
2
3
4
5

int val;

TreeNode *left;

TreeNode *right;

TreeNode() : val(0), left(NULL), right(NULL) {}

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
1
2
3
4
5
6
7
8
9
10
11

int n,count=0;

char item[100];

cin>>n;

if (n==0)

    return NULL;

cin>>item;

TreeNode* root = new TreeNode(atoi(item));

count++;

queue nodeQueue;

nodeQueue.push(root);

while (count>item;

    count++;

    if (strcmp(item,"null")!=0)

    {

        int leftNumber = atoi(item);

        node->left = new TreeNode(leftNumber);

        nodeQueue.push(node->left);

    }

    if (count==n)

        break;

    cin>>item;

    count++;

    if (strcmp(item,"null")!=0)

    {

        int rightNumber = atoi(item);

        node->right = new TreeNode(rightNumber);

        nodeQueue.push(node->right);

    }

}

return root;
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

TreeNode* root;

root=inputTree();

int sum;

cin>>sum;

int res=Solution().pathSum(root,sum);

cout<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

}

2.输入说明
首先输入结点的数目n（注意，这里的结点包括题中的null空结点）

然后输入n个结点的数据，需要填充为空的结点，输入null。

最后输入一个整数sum。
3.输出说明
输出一个整数，表示结果。
4.范例
输入
11
10 5 -3 3 2 null 11 3 -2 null 1
8
输出
3
5.代码

#include 

#include 

#include 

#include 

#include

using namespace std;

struct TreeNode

{

	int val;

	TreeNode *left;

	TreeNode *right;

	TreeNode() : val(0), left(NULL), right(NULL) {}

	TreeNode(int x) : val(x), left(NULL), right(NULL) {}

	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

TreeNode* inputTree()

{

	int n, count = 0;

	char item[100];

	cin >> n;

	if (n == 0)

		return NULL;

	cin >> item;

	TreeNode* root = new TreeNode(atoi(item));

	count++;

	queue<TreeNode*> nodeQueue;

	nodeQueue.push(root);

	while (count < n)

	{

		TreeNode* node = nodeQueue.front();

		nodeQueue.pop();

		cin >> item;

		count++;

		if (strcmp(item, "null") != 0)

		{

			int leftNumber = atoi(item);

			node->left = new TreeNode(leftNumber);

			nodeQueue.push(node->left);

		}

		if (count == n)

			break;

		cin >> item;

		count++;

		if (strcmp(item, "null") != 0)

		{

			int rightNumber = atoi(item);

			node->right = new TreeNode(rightNumber);

			nodeQueue.push(node->right);

		}

	}

	return root;

}

int rootSum(TreeNode *root, int sum)
{
	
	if (!root)//空树
		return 0;
	
	int res = 0;
	if (root->val == sum)//根节点正好等于sum 
		res++;

	res += rootSum(root->left, sum - root->val);//继续遍历左子树
	res += rootSum(root->right, sum - root->val);//继续遍历右子树
	return res;
}


int pathSum(TreeNode *root, int sum)
{
	
	if (!root)
		return 0;
	
	int res = rootSum(root, sum);//以该根节点开始遍历
	res += pathSum(root->left, sum);//以左子树为根节点开始遍历
	res += pathSum(root->right, sum);//以右子树为根节点开始遍历
	return res;
}


int main()

{

	TreeNode* root;

	root = inputTree();

	int sum;

	cin >> sum;

	int res = pathSum(root, sum);

	cout << res << endl;

}


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