1110 Complete Binary Tree

Given a tree, you are supposed to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a 

-

 will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each case, print in one line 

YES

 and the index of the last node if the tree is a complete binary tree, or 

NO

 and the index of the root if not. There must be exactly one space separating the word and the number.

Sample Input 1:

9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -
           

Sample Output 1:

YES 8
           

Sample Input 2:

8
- -
4 5
0 6
- -
2 3
- 7
- -
- -
           

Sample Output 2:

NO 1           

题意：

　　给出一棵树中各个结点的左右孩子的信息，判断这棵树是不是完全二叉树，如果是，输出最后一个结点的下标，如果不是，输出根节点的下标。

思路：

　　刚开始想的是把这棵树给构建出来，然后按照要求输出就好了，但是，这样做有三组测试样例不能通过。（找到错误的原因了，是我把字符串转数字的函数写错了，其实可以不用写的，直接用stoi()函数就好了）然后，看了一下别人的代码，发现可以不用构建树，就可以做出来。（既然我的代码已经通过了，就把我的写上去吧，哈哈哈）

1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 map<int, pair<int, int> > m;
 6 
 7 typedef struct Node* node;
 8 
 9 struct Node {
10     int val;
11     node left;
12     node right;
13     Node(int v) {
14         val = v;
15         left = NULL;
16         right = NULL;
17     }
18 };
19 
20 int lastNode(node root) {
21     queue<node> que;
22     que.push(root);
23     bool haveEnd = false;
24     node temp;
25     while (!que.empty()) {
26         temp = que.front();
27         que.pop();
28         if (temp->left != NULL) {
29             if (haveEnd) return -1;
30             que.push(temp->left);
31         } else
32             haveEnd = true;
33         if (temp->right != NULL) {
34             if (haveEnd) return -1;
35             que.push(temp->right);
36         } else
37             haveEnd = true;
38     }
39     return temp->val;
40 }
41 
42 node buildTree(int r) {
43     if (r < 0) return NULL;
44     node root = new Node(r);
45     if (m.find(r) != m.end() && m[r].first != -1) 
46         root->left = buildTree(m[r].first);
47     if (m.find(r) != m.end() && m[r].second != -1) 
48         root->right = buildTree(m[r].second);
49     return root;
50 }
51 
52 int main() {
53     int n;
54     cin >> n;
55     vector<bool> haveParent(n, false);
56     for (int i = 0; i < n; ++i) {
57         string left, right;
58         cin >> left >> right;
59         pair<int, int> temp = {-1, -1};
60         if (left[0] != '-') {
61             int l = stoi(left);
62             haveParent[l] = true;
63             temp.first = l;
64         }
65         if (right[0] != '-') {
66             int r = stoi(right);
67             haveParent[r] = true;
68             temp.second = r;
69         }
70         m[i] = temp;
71     }
72 
73     int r = 0;
74     while(haveParent[r]) r++;
75 
76     node root = buildTree(r);
77     int last = lastNode(root);
78     if (last < 0)
79         cout << "NO " << root->val << endl;
80     else
81         cout << "YES " << last << endl;
82 
83     return 0;
84 }      

永远渴望，大智若愚（stay hungry, stay foolish）