PAT-Advanced-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 (<=20) 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:

Sample Output 1:

Sample Input 2:

Sample Output 2:

仿效了二项堆的存储方式来存储 Complete Binary Tree ,这样就可以很方便的判断是否是一颗 Complete Binary Tree 以及确定最后一个节点是什么……

代码如下:

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注