力扣练习——43 路径总和

43 路径总和

1.问题描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:

给定如下二叉树，以及目标和 sum = 22，

          5

         / \

        4   8

       /    /  \

     11  13  4

    /  \      \

   7    2      1
1
2
3
4
5
6
7
8
9
10
11
12
13

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

可使用以下main函数：

#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) {}
1
2
3
4
5
6
7
8
9
10
11

};

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 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

}

int main()

{

TreeNode* root;

root=inputTree();

int sum;

cin>>sum;

bool res=Solution().hasPathSum(root,sum);

cout<<(res?"true":"false");
1
2
3
4
5
6
7
8
9
10
11

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

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

最后输入一个整数sum。
3.输出说明
输出true或false
4.范例
输入
13
5 4 8 11 null 13 4 7 2 null null null 1
22
输出
true
5.代码

#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;

}

bool hasPathSum(TreeNode* root, int sum)
{
	if (!root)return false;
	//记录结点
	queue<TreeNode*>q;
	//记录已经遍历得到结点相加值
	queue<int>q_val;
    //接下来根节点入队，别忘记
	q.push(root);
	q_val.push(root->val);
	//遍历
	while (!q.empty())
	{
		TreeNode *node = q.front();//队头元素
		q.pop();//出队
		int node_val = q_val.front();
		q_val.pop();
		if (node->left == NULL && node->right == NULL)//叶子结点
		{
			if (node_val == sum)
				return true;
			continue;//若不满足,跳过
		}
		//左子树非空
		if (node->left != NULL)
		{
			q.push(node->left);//左节点入队
			q_val.push(node->left->val + node_val);//更新队列元素值
		}
		//右子树非空
		if (node->right != NULL)
		{
			q.push(node->right);//左节点入队
			q_val.push(node->right->val + node_val);//更新队列元素值
		}

	}
	return false;
}

int main()

{

	TreeNode* root;

	root = inputTree();

	int sum;

	cin >> sum;

	bool res = hasPathSum(root, sum);

	cout << (res ? "true" : "false");

}


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