二叉树的遍历

关于二叉树的遍历，往往会出这么几类题目：

1. 根据一种序列重建二叉树

分析：只给出一个输出序列会对应多种二叉树，因此这类题目的给定序列中往往包含有空节点，这时只需要反过来写递归程序便可：
例：1086 Tree Traversals Again (25)（25 分）
程：

int times = 0;                //计数变量
node * build()
{
    node * r = NULL;         //根节点指针
    if( times < 2*N )            //若输入N个数据，则二叉树有2*N个节点    
    {
        int tem;            
        cin >> tem;
        if( tem !=  -1 )        //若输入不是-1
        {
            r = new node;    
            r -> num = tem;    //建立根节点
            times++;
        }
        else
        {                    //若是-1
            times++;
            return NULL;    //返回空指针
        }
            r->left = build();        //递归调用 ,建立leftchild
            r->right = build();    //递归调用,建立rightchild
    }
    return r;                //返回建立好的二叉树(pre-order)
}

2.根据先序中序遍历

分析： 既然给出了两种序列，那么序列中一定不包含空节点的输出，对于这种问题其解题的核心在于找到根节点位置。
那么，如何找到根节点的位置呢？这就得利用中序遍历序列了。
例：1138 Postorder Traversal（25 分）
程：

void build(int root, int start, int end)
{
    if(start > end)
        return;
    int i = start;
    for(; inorder[i] != post[root]); i++);
    /************************
            do something
    ************************/
    build( root + 1,start,i-1);
    build( root + (i-start) + 1, i+1 , end);
}

析：
例如先序与中序分别是是:

1 2 3 4 5 6 7
2 3 1 5 4 7 6

根据先序序列，我们能够知道，根节点是1，那么2节点是1的左孩子(先序遍历的特性)。那么右节点在哪呢?
如果我们再看看中序序列，我们就可以清楚地发现树的结构是这样的：

           1
{2 3}          {5 4 7 6}

所以，先序序列的排布方式会是这样：

根 |   左   |      右 
 1  | 2   3  | 4   5   6   7

递归程序的接口设计为根节点的位置(先序)，树的范围(中序)。
根据中序序列确定子树的范围和子树的根节点位置。

3.根据先序后序遍历

例:1119 Pre-and Post-order Traversals（30 分）
程:

void build(int preStart, int preEnd, int postStart, int postEnd)
{       
        if(preStart == preEnd)
        {
                v.push_back(preorder[preStart]);        
                return ;
        }
        if(preorder[preStart] == postorder[postEnd])
        {
                int i = preStart + 1;
                for(; i < preEnd && preorder[i] != postorder[postEnd-1]; i++); // find the root of right child in preorder sequence
                if(i - preStart > 1)
                        build(preStart + 1,i-1,postStart,postStart+(i - preStart-1) - 1);
                else
                        unique = false;
                v.push_back(preorder[preStart]);
                build(i,preEnd,postStart + (i - preStart-1),postEnd - 1);
        }
}

析：首先需要说明的是，根据先序与后序而确定的二叉树并不唯一。
解决这个问题的核心在于树的划分。