Uva 839天平（二叉树dfs， 递归建树）

题意：

给定一个天平长度 输入格式为

wl dl wr dr

分别代表天平左边长度，左边重量， 右边长度， 右边重量。

如果重量为0， 说明下面还有一个天平， 递归给出。

样例输入：
1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

如果天平是左右重量相等的 输出YES 否则输出NO。

分析：

既然以递归的定义输入， 那么我们程序最好写成递归建树，如果有重量是0， 那么就递归建左子树或者右子树 ， 如果是叶子节点的父节点（这个天平下面没天平）， 那么就判断左右是否相等返回即可（也可建一个全局变量， 一个不满足就可以输出NO了）。 我的程序是把树建造出来再判断， 有点冗余。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6;

struct Node{

  int wl,dl,wr,dr;

  int left, right;

  Node():wl(),dl(),wr(),dr(){}

};

Node tree[maxn];

const int root = ;

int cnt = , ok;

int build(int u){

    int wl,dl,dr,wr;

    scanf("%d %d %d %d",&wl,&dl,&wr,&dr);

    tree[u].wl = wl;

    tree[u].dl = dl;

    tree[u].wr = wr;

    tree[u].dr = dr;

    if(!wl) {

            tree[u].left = ++cnt;

            build(cnt);

    }

    if(!wr) {

            tree[u].right = ++cnt;

            build(cnt);

    }

}

int post(int u){

    if(!tree[u].wl) {

        tree[u].wl = post(tree[u].left);

    }

    if(!tree[u].wr) {

        tree[u].wr = post(tree[u].right);

    }

    if(tree[u].wl * tree[u].dl != tree[u].wr * tree[u].dr)

         ok = ;

    return tree[u].wl + tree[u].wr;

}

int main(){

    int T;

    scanf("%d", &T);

    int flag = ;

    while(T--){

        if(!flag){

            flag = ;

        }

        else printf("\n");

        cnt = root;

        build(root);

        ok = ;

        post(root);

        printf("%s\n",ok ? "YES":"NO");

    }

    return ;

}