博客

紫书刷题进行中，题解系列【

GitHub

|

CSDN

】

例题6-7 UVA122 Trees on the level（57行AC代码）

题目大意

给定若干个节点，构建一个二叉树，层次遍历打印结点值。其中结点值和位置以

(value,path)

，value为整型值，path为从根到当前结点的路径，如

LRR

，表示

左右右

。

思路分析

很常规的问题，分割字符串得到值和路径，在构建树的过程中注意创建没有的结点，定义结点的结构体如下，其中

assignCnt

记录当前结点被赋值的次数，便于处理未赋值和多次赋值情况。这里不写默认构造函数，而是直接给结构体成员赋初始值（偷个懒：）

struct Node {
    int val, assignCnt=0; // 值，被赋值次数
    Node *l=NULL, *r=NULL; // 左右子树
};

层次遍历用一个队列处理即可

注意点

• 树根必须先创建结点，否则树根一直指向空，导致后续建树无法连接
• 建树过程中，注意左右子树若为空，必须以
  
root->l=new Node

  方式创建结点，否则先
  
root=root->l

  再
  
root=new Node

  将导致树连接断裂
• 以上两种均导致建树失败，注意指针和引用区别，传值和传址

AC代码（C++11，建树，层次遍历）

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int val, assignCnt=0; // 值，被赋值次数
    Node *l=NULL, *r=NULL; // 左右子树
};
Node* btree=NULL; // 二叉树根
void insertNode(string s, Node* root) { // 根据路径s插入节点
    int i = s.find(',');
    string ds=s.substr(i+1,s.size()-i-1-1); // 方向
    for (int j=0; j < ds.size();  j++) { // 遍历路径
        if (ds[j] == 'L') {
            if (root->l == NULL) root->l = new Node; // 必须创建节点，否则连接会断开
            root = root->l;
        }
        else if (ds[j] == 'R') {
            if (root->r == NULL) root->r = new Node;
            root = root->r;
        }
    }
    root->val = stoi(s.substr(1,i)); // 赋值
    root->assignCnt ++; // 赋值次数累计
}
void layerTra(Node* root) { // 层次遍历
    bool isLegal=true; // 标记是否合法：每个点仅赋值一次
    vector<int> out; // 层次遍历输出存储
    queue<Node*> q; // 遍历队列
    if (root != NULL) q.push(root); // 初始化
    while (!q.empty() && isLegal) {
        Node* node = q.front(); q.pop();
        if (node->assignCnt != 1) isLegal = false; // 非法：赋值0或多次
        else {
            out.push_back(node->val);
            if (node->l != NULL) q.push(node->l); // 非空压入左右子树
            if (node->r != NULL) q.push(node->r);
        }
    }
    if (isLegal) { // 合法输出
        for (int i=0; i < out.size(); i ++) 
            printf("%d%s", out[i], i == out.size()-1 ? "\n" : " ");
    }
    else printf("not complete\n");
}
int main() {
    string s;
    while (cin >>s) {
        if (s == "()") {
            layerTra(btree);
            btree=NULL; // 此处可改为递归释放内存，偷个懒，不写了
        }
        else {
            if (btree == NULL) btree = new Node; // 根必须先创建，否则是空值则无法连接节点
            insertNode(s, btree);
        }
    }
    return 0;
}