PAT（甲级）1110 Complete Binary Tree (25point(s)) 判断是不是完全二叉树

ゝ一世哀愁。 2024-05-08 06:03 75阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

**题目大意**：给一颗二叉树，判断是不是完全二叉树；  
可以根据完全二叉树的性质来判断，在线性存储结构下，左孩子下标 = 2 \* 父节点下标， 右孩子下标 = 2 \* 父节点下标+ 1；  
我们在输入节点过程中，如果一个节点是别人的孩子节点，那么他一定不是根节点，这样在输入完成后，在遍历一遍所有节点，就可以找到根节点；  
然后从这个根节点出发开始DFS，输入两个参数，一个是这个节点的id，另一个是这个节点如果在线性表中应有的下标，如果下标大于全局最大值，那么更新最大值，并且记录这个节点的id，作为最后一个节点;  
最后根据最大的下标是否等于节点个数判断是不是完全二叉树；

##### 代码 #####

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <set>
    
    using namespace std;
    const int maxn = 30;
    
    struct node{
        
         int left, right;
         node(){
        
              this->left = -1, this->right = -1;
         }
    }tree[maxn];
    bool isRoot[maxn];//存储是不是根节点，如果读入过程中发现是叶节点，则标记为不是根节点
    int last = -1, ans;//ans 记录最后一个节点,last记录最后一个节点在线性表的下标
    //遍历每个节点，idx是当前这个节点的在线性表的下标，找到下标最大的数
    void DFS(int root, int idx){
        
         if(idx > last){
        
              last = idx;
              ans = root;
         }
         //递归时注意判断一下，在叶节点就结束，而不是叶节点的下一层
         if(tree[root].left != -1) DFS(tree[root].left, 2 * idx);
         if(tree[root].right != -1) DFS(tree[root].right, 2 * idx + 1);
    }
    
    int main()
    {
        
         fill(isRoot, isRoot + maxn, true);
         int n;
         scanf("%d", &n);
         string l, r;
         for(int i = 0; i < n; i ++){
        
              cin >> l >> r;
              if(l != "-"){
        
                   tree[i].left = stoi(l);
                   isRoot[stoi(l)] = false;//标记不是根节点
              }
              if(r != "-"){
        
                   tree[i].right = stoi(r);
                   isRoot[stoi(r)] = false;
              }
         }
         int root = 0;
         while(isRoot[root] == false) root ++;//找到根节点
         DFS(root, 1);
         if(last == n) printf("YES %d\n", ans);
         else printf("NO %d\n", root);
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805359372255232