6 7 trees_on_the_level_uva122） - nuaazdh/acm GitHub Wiki

##例题6-7 二叉树层次遍历（Trees on the level UVa122） ###问题 按(n,s)格式给定一个二叉树，其中n为二叉树节点的值，s为该节点相对于根节点的位置，L表示左子树，R表示右子树， LL表示左子树的左子结点，以此类推。() 标识当前二叉树结束， 程序的输入以EOF结束。二叉树的结点个数不大于256。 输出二叉树的层次遍历结果，如果存在未赋值的结点，或者结点的值重复出现，输出not complete。

样例输入

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

样例输出

5 4 8 11 13 4 7 2 1
not complete

###分析

二叉树的层次遍历非常简单，使用队列来实现即可。如何存储这个二叉树？数组？因为此题二叉树不保证完全二叉树，数组存储太大了（比如只有左子树的情况）。因此还是要动态申请空间。

二叉树的结点结构体的定义，可以参照leetcode上的常见定义方式：

struct TreeNode {
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

###code in C++

#include <iostream>
#include <vector>

struct btnode {
    int val;
    btnode *left;
    btnode *right;

    btnode(int v) : val(v), left(NULL), right(NULL) { }
};

void tree_on_level(btnode *root) {
    std::vector<btnode *> tree;
    bool flag = true;
    tree.push_back(root);
    int i = 0;
    while (1) {
        if (i > tree.size() - 1) {
            break;
        }
        if (tree[i] == NULL) {
            flag = false;
            break;
        }
        if (tree[i]->val == 0) {
            flag = false;
            break;
        }
//        std::cout<<"root: "<<tree[i]->val;
        if (tree[i]->left) {
            tree.push_back(tree[i]->left);
//            std::cout<<"\tleft:"<<tree[i]->left->val;
        }
        if (tree[i]->right) {
            tree.push_back(tree[i]->right);
//            std::cout<<"\tright:"<<tree[i]->right->val<<"\n";
        }
        ++i;
    }
    if (flag) {
        for (i = 0; i < tree.size(); ++i) {
            if (i) std::cout << " ";
            std::cout << tree[i]->val;
            delete tree[i];
        }
    } else {
        std::cout << "not complete";
    }
    std::cout << "\n";
}

int main() {
    std::string line;
    while (std::cin >> line) {
        btnode *root = new btnode(0);
        bool valid = true;
        do {
            int val = 0;
            int i;
            for (i = 1; i < line.length() && line[i] != ','; ++i) {
                val = val * 10 + (line[i] - '0');
            }
            if (val == 0) { valid = false; }
            btnode *ptr = root;
            for (++i; i < line.length(); ++i) {
                if (line[i] == 'L') {
                    if (ptr->left == NULL) {
                        ptr->left = new btnode(0);
                    }
                    ptr = ptr->left;
                } else if (line[i] == 'R') {
                    if (ptr->right == NULL) {
                        ptr->right = new btnode(0);
                    }
                    ptr = ptr->right;
                } else {

                }
            }
            if (ptr->val != 0) {
                valid = false;
            }
            ptr->val = val;
        } while (std::cin >> line && line != "()");
        if (valid) tree_on_level(root);
        else {
            std::cout << "not complete\n";
        }
    }
}

###点评

  1. 注意在 do{}while中不能使用局部变量给 node 的结点赋值，因为循环内的变量作用域有限；
  2. 使用了个技巧，不在需要queue，而是vector实现了queue的功能；
⚠️ **GitHub.com Fallback** ⚠️