6 9_not_so_mobile_uva839 - nuaazdh/acm GitHub Wiki

##例题6-9 天平（Not so mobile UVa839) ###问题 天平平衡满足 Wl*Dl = Wr*Dr。现在以一个二叉树的形式给定一个天平，每一行给定四个数，分别为Wl、Dl、Wr和Dr，如果W为零，表示存在子树。 第一行给定测试case 的数目，后面跟着一个空行，然后每个测试case 以空行分开。 每行四个数值。若存在子树，则左子树在先。

样例输入

1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

样例输出

YES

###分析 一个天平平衡，首先每个子树平衡，然后子树的总和作为根节点的W值，最后保证根节点的左右子树平衡即可。 如何根据输入建立起一棵树，采用递归的形式，读入一行，若存在W值为零，下一行就是左子树，对左子树中存在为零的W也是这样处理。若没有子树，先判断是否平衡，然后返回总的W。

code in C++

#include <stdio.h>

int is_balance = 1;

int balance() {
    int wl, dl, wr, dr;
    scanf("%d%d%d%d",&wl,&dl,&wr,&dr);
    if (wl == 0) {
        wl = balance();
    }
    if (wr == 0) {
        wr = balance();
    }
    if (wl * dl != wr * dr) {
        is_balance = 0;
    }
    return wl + wr;
}

int main() {
    int T;
    scanf("%d",&T);
    while (T--) {
        is_balance = 1;
        balance();
        if (is_balance) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
        if(T) printf("\n");
    }
    return 0;
}

###点评

  1. 设置一个全局变量来记录是否平衡，注意每次都要清楚这个变量；
  2. 注意当子树不平衡时，仅仅是设置下全局变量，仍要把全部输入读完，不能中途break或返回；
⚠️ **GitHub.com Fallback** ⚠️