这题主要算法最多普及-，输入的难度个人认为高达省选！（调输入的时间占做这题时间的九成！！！）

题目描述

给出一棵整数的二叉树，请写一个程序判定是否存在这样一条从树根到树叶的路，路上的结点的总和等于一个特定的整数。

这道题极其坑人的的点在判断两个儿子是否都为叶节点和输入上。

0x01 树的遍历

这里推荐使用在线算法，因为写起来简单。

很容易发现在每次读入数时，我们就到达了一个叶节点或一颗子树的根节点，这个时候可以加和，等到该节点的子树遍历完之后像自己的父亲，也就是上一个节点回溯。回溯的过程很简单，就是把当前的加和减去现在节点的值。

1
2
3
4
5
6
//sign 是负数的标志
cin>>po;
sum+=po*sign;
dfs(dep+1);
dfs(dep+1);
sum-=po*sign;

那么，知道了如何加和，那如何比较结果呢？

对于这道题，显然是在叶子节点处比较结果。那么，如何判断是否为叶子结点呢？

0x02 判断是否为叶子节点

根据题意，叶子节点的格式是这样的：(num()())，要想判断叶子节点，就要判断两个空树。

方法一：如果读入第一个 ( 后在探测下几个字符（探测的用法下一个部分要讲），如果为 )() 那就成功判断一个叶节点。

但是 C++ 自带的探测函数指针不后移，如果后移的话像 ()(...) 这样的数据就会过度输入，对后面的遍历产生影响。

方法二：只探测每个树第一个 ( 后是否为 )，如果是，就返回 11，如果一个节点的左右子树都是空树，那么才进行现在的加和与给定的数的比较。当然，探测到 ) 后要指针后移，避免在下次遍历的开始读到右括号从而影响遍历。

1
2
3
4
5
6
7
8
9
10
if(cin.peek()==')'){//探测下一个字符是否为')'
	cin.ignore();//指针后移
	return (sum==n);//可以返回 1，也可以直接返回比较结果
}
//...
temp+=dfs(dep+1);
temp+=dfs(dep+1);
if(temp==2){//如果在上面返回 1，这里就要进行比较
	flag=1;
}

那么这样的话，我们的递归函数的返回值就是该节点是否为子树，需要一个新的变量来存比较的结果。

主要算法都讲完了，但先别急，因为这道题的输入可以让你爆炸！！！

0x03 输入

我推荐的方法是用探测和指针后移的方式来实现左右括号的读入与判断。

先介绍函数，探测函数是 cin.peek()，这个函数返回该指针的下一个字符。后移函数是 cin.ignore()，这个函数使当前输入的指针后移一位。读入的时候就从后移后的下一个字符开始读入，后移后指针所指的字符不读入。

首先，我们要实现对于空格和换行的跳过：

1
2
3
void space(){
	while(cin.peek()<=32)cin.ignore();//' ','\n','\r'的ASCII值都小于等于32
}

然后我们就在想要探测并跳过左右括号或者负号时，先去空格等字符，然后读入，判断，跳过就行了（但是很容易写错！！！）。

完整 AC 代码：

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
#include<bits/stdc++.h>
using namespace std;
char k,kk;
long long n;
long long sum=0;
bool flag=0;
void space(){
	while(cin.peek()<=32)cin.ignore();
}
bool dfs(long long dep){
	long long po;
	long long temp=0;
	space();
	cin.ignore();
	space();
	if(cin.peek()==')'){
		cin.ignore();
		return (sum==n);
	}
	int sign=1;
	if(cin.peek()=='-'){
		sign=-1;
		cin.ignore();
	}
	space();
	cin>>po;
	sum+=po*sign;
	temp+=dfs(dep+1);
	temp+=dfs(dep+1);
	if(temp==2){
		flag=1;
	}
	sum-=po*sign;
	space();
	cin.ignore();
	return 0;
}
string s;
int main(){
	int u=0;
	while(cin>>n){
		flag=0;
		dfs(1);
		s=(flag)?"yes":"no";
		cout<<s<<endl;
	}
}