首页 > 代码库 > UVA112

UVA112

//题目意思就遍历树,从根节点到叶子节点的和是否等于输入的数,空树一定是no

//只是树长的有点奇怪,

//解题思路

在纸上画出树的图形,节点到左孩子的输入是(,孩子回到父亲节点的输入是),一对()代表该节点没有

在进入第一个节点的时候把 ( 前缀 读了,保证在进入孩子节点前把(前缀读取了即可
 if(lbNum!=0)
  c = read();
记录左括号数目,防止读多和读少,防止下一个树出错
#include <iostream>
#include<stdio.h>
using namespace std;




char read()
{
    char c;
    cin>>c;
    return c;
}



int findLeaf(int total,int n,int& m,int lbNum)
{
    int d;
    char c;
    cin>>d;
    bool readOk = true;
    if(cin.fail())
    {
        cin.clear();
        //c = read();
        readOk = false;
    }
    c = read();
    if(!readOk)
    {
        return 1;
    }
    if(c==‘(‘)
    {
        bool leftNull=false,rightNull=false;
        //左孩子
        if(findLeaf(total+d,n,m,lbNum+1)==1)
        {
            leftNull = true;
            c = read();
        }
        //右孩子
        if(findLeaf(total+d,n,m,lbNum+1)==1)
        {
            rightNull = true;
            c = read();
        }
        if(lbNum!=0)
        c = read();
        if(leftNull&&rightNull)
        {
            if(total+d==n)
            {
                m = 1;
                return 0;
            }
        }
    }
    return 0;
}

int main()
{
   freopen("d:\\1.txt","r",stdin);
    int n;
    while(cin>>n)
    {
        int m=0;
        read();
        findLeaf(0,n,m,0);
        if(m)
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}

  

UVA112