二叉树专题 Tree Summing

小灰灰 2022-06-13 10:16 189阅读 0赞

LISP was one of the earliest high-level programming languages and, with FORTRAN, is one of the oldest languages currently being used. Lists, which are the fundamental data structures in LISP, can easily be adapted to represent other important data structures such as trees.  
  
This problem deals with determining whether binary trees represented as LISP S-expressions possess a certain property.  
Given a binary tree of integers, you are to write a program that determines whether there exists a root-to-leaf path whose nodes sum to a specified integer. For example, in the tree shown below there are exactly four root-to-leaf paths. The sums of the paths are 27, 22, 26, and 18.  
![1145_1.gif][]  
Binary trees are represented in the input file as LISP S-expressions having the following form.

empty tree ::= ()
    
    tree 	   ::= empty tree (integer tree tree)

The tree diagrammed above is represented by the expression (5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )  
  
Note that with this formulation all leaves of a tree are of the form (integer () () )  
  
Since an empty tree has no root-to-leaf paths, any query as to whether a path exists whose sum is a specified integer in an empty tree must be answered negatively.

输入

The input consists of a sequence of test cases in the form of integer/tree pairs. Each test case consists of an integer followed by one or more spaces followed by a binary tree formatted as an S-expression as described above. All binary tree S-expressions will be valid, but expressions may be spread over several lines and may contain spaces. There will be one or more test cases in an input file, and input is terminated by end-of-file.

输出

There should be one line of output for each test case (integer/tree pair) in the input file. For each pair I,T (I represents the integer, T represents the tree) the output is the string yes if there is a root-to-leaf path in T whose sum is I and no if there is no path in T whose sum is I.

样例输入

22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
    20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
    10 (3 
         (2 (4 () () )
            (8 () () ) )
         (1 (6 () () )
            (4 () () ) ) )
    5 ()

样例输出

yes
    no
    yes
    no

来源

Duke Internet Programming Contest 1992,UVA 112

一道很简单的二叉树问题

即根据题意建立一颗二叉树，然后求从根节点到叶子几点路径上的值的和 看那个和有没有出现过

参考网上某个写的很清晰的代码

比较好的地方是其对于 读入的处理

由于读入的时候会有很多空格或者换行，那么怎么处理呢？比较好的方法就是一直读char，如果该char不是我们期盼的要处理的char，那么就一直读下去，这个思路很好

自己实现的时候由于不注意空节点的处理导致出现了错误WA，具体是什么样的情形懒得想了，就是注意以后在建树的时候要注意对空节点的处理

代码如下

// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<memory.h>
    using namespace std;
    int num;
    int ans[1 << 20];
    int tot;
    struct node
    {
    	int val;
    	node* l;
    	node* r;
    
    	node(int x=0)
    	{
    		val = x;
    		l = NULL;
    		r = NULL;
    	}
    };
    
    node* build()
    {
    	char c;
    	node* root1 = new node;
    	int cnt = 0;  //初始化
    	int x = 0;
    	bool bo = true;
    	while (scanf("%c",&c)!=EOF) //对字符进行处理
    	{
    	
    		if (c >= '0' && c <= '9') //数字的话一定和val有关，不停的加到上面去
    		{
    			x = x * 10 + c - '0';
    			continue;
    		}
    		if (c == '(' && cnt==0) //判断是第一个（还是第二个（，从而决定是左子树还是右子树
    		{
    			cnt++;
    			root1->l = build();
    			continue;
    		}
    		if (c == '(' && cnt == 1)
    		{
    			root1->r = build();
    			continue;
    		}
    		if (c == ')') //碰到右括号就算结束了其建立
    		{
    			break;
    		}
    		if (c == '-') //碰到-那么就是有负号，结果变为负数
    		{
    			bo = false;
    			continue;
    		}
    	}
    	if (!bo) x = -x;
    	root1->val = x;
    	if (cnt == 0 && root1->val == 0) return NULL;  //很重要，如果该节点是NULL，那么必须要返回空？？否则会出错
    	return root1;
    }
    void dfs(node* n, int sum)
    {
    	if (n == NULL) return;  //如果是NULL节点，不做任何操作
    	if (n->l == NULL && n->r == NULL) //如果是叶子节点，填入
    	{
    		ans[tot++] = sum + n->val;
    		return;
    	}
    	if (n->l != NULL) dfs(n->l, sum + n->val);
    	if (n->r != NULL) dfs(n->r, sum + n->val);
    }
    
    
    int main()
    {
    	char c;
    	while (scanf("%d", &num) != EOF)  //不停的读入数字， 如果不是空就接着读
    	{
    		tot = 0;   //tot这个变量是代表有多少叶子节点， 然后把每个叶子节点上的结果都存到ans数组中
    		memset(ans, -1, sizeof(ans));  //这里是对ans的初始化，其实没有必要，因为每次都覆盖了
    		node* root = new node;  //声明根节点
    		while (scanf("%c", &c)!=EOF)
    		if (c == '(')     //不停的读，一直到碰到第一个(
    		{
    			root = build();  //递归处理，将括号里的处理完后，建立一棵树赋给root
    			break; //第一次读到（后就应该break
    		}
    
    		dfs(root, 0);  //对树进行一下遍历，求得每个叶子节点上的结果
    		bool bo = true;
    		for (int i=0; i<tot; i++)
    			if (ans[i] == num)
    			{
    				bo = false;
    				break;
    			}
    		if (bo) printf("no\n");
    		else printf("yes\n");
    	}
        return 0;
    }

[1145_1.gif]: /images/20220613/96b9aeb3c0534e6791ed41be36b61cf9.png