二叉树相关算法：重构与层次遍历

二叉树的重构——需要至少有中序遍历序列，以及前序后序任意一个

基本思路：以下以L表示左子树/左孩子，V表示当前节点，R表示右子树/右孩子，这里以中序+后序为例

中序遍历序列顺序为LVR，后序遍历序列顺序为LRV，因此可以直接从后序遍历序列中找出根节点V，即序列中的最后一个元素

然后以V为分界，对中序遍历序列进行分割——可以很容易地看出，V左侧即为左子树的中序遍历序列，右侧即为右子树的中序遍历序列

同样的长度可以用于分割后序遍历序列，依次得到左右子树的两个序列

接下来对两个子树进行递归调用即可

演示代码：

using namespace std;
typedef struct Node {
    Node * lchild;
    Node * rchild;
    int data;
}Node;
int post[31]; //LRV
int in[31]; //LVR
Node *tree;

void buildTree(int p1, int p2, int i1, int i2, Node* &treeNode) {
    if (treeNode==NULL)
    {
        treeNode = new Node();
    }
    if (p1>p2||i1>i2)
    {
        return;
    }
    //cout << “flag”<< endl;
    treeNode->lchild = NULL;
    treeNode->rchild = NULL;
    treeNode->data = post[p2];
    //cout <<post[p2] << endl;
    int count = p1;
    int i;
    for ( i =i1 ; i <=i2; i++, count++)
    {
        if (post[p2] == in[i]) { //V found
            break;
        }
        
    }
    buildTree(p1, count – 1, i1, i – 1, treeNode->lchild);
    buildTree(count, p2 – 1, i + 1, i2, treeNode->rchild);
}//注意边界值

二叉树的层次遍历：

新建一个辅助队列，将根节点入队，然后出队

对根节点进行访问——同时，如果根节点存在后代的话，按照左右孩子的顺序依次入队

循环进行此操作，直至整个队列彻底为空再停止

演示代码：

    queue<Node*>level;
    level.push(tree);
    vector<int>output;
    while (!level.empty())
    {
        if (level.front()->data)
        {
            int number = level.front()->data;
//            cout << number << endl;
            output.push_back(number);
        }

        if (level.front()->lchild!=NULL)
        {
            level.push(level.front()->lchild);
        }
        if (level.front()->rchild!=NULL)
        {
            level.push(level.front()->rchild);
        }
        level.pop();
    }