通過樹的先序和中序遍歷序列來構造二叉樹

題目：給出一棵二叉樹的先序和中序遍歷的序列，構造出該二叉樹。

思路一：采用分治法。

1）取先序遍歷序列的第一個值，用該值構造根結點，，然後在中序遍歷序列中查找與該元素相等的值，這樣就可以把序列分為三部分：左子樹（如果有）、根結點和右子樹（如果有）。

2）將兩個序列都分成三部分，這樣就分別形成了根結點的左子樹和右子樹的先序遍歷和後序遍歷的序列。

3）重復1）和2）步驟，直至所有結點都處理完就可以完整構成一顆二叉樹了。

根據分治法構造二叉樹的代碼實現：

TreeNode *buildTree(vector &preorder, vector &inorder)
{
        if(preorder.empty() && inorder.empty())
            return NULL;
        int root_val = preorder[0];//該子樹根結點的元素值為先序遍歷的第一個元素
        TreeNode* root = new TreeNode(root_val);//創建該子樹的根結點
        vector preorderL, preorderR, inorderL, inorderR;
        vector::iterator it, it_a;//在中序遍歷中查找根結點元素
        int i = 0;
        it = inorder.begin();
        while(*it != root_val)
        {
            it++;
            i++;
        }

        //確定中序遍歷的左右子樹序列
        for(it_a = inorder.begin(); it_a != it; it_a++)
            inorderL.push_back(*it_a);
        for(it_a = it+1; it_a != inorder.end(); it_a++)
            inorderR.push_back(*it_a);
        //確定前序遍歷的左右子樹序列
        it = preorder.begin();
        while(i)
        {
            it++;
            i--;
        }

        for(it_a = preorder.begin()+1; it_a != it+1; it_a++)
            preorderL.push_back(*it_a);
        for(it_a = it+1; it_a != preorder.end(); it_a++)
            preorderR.push_back(*it_a);

        //迭代構造二叉樹
        root->left = buildTree(preorderL, inorderL);
        root->right = buildTree(preorderR, inorderR);

        return root;
}

Memory Limit Exceeded

思路二：用棧來實現。

1）用先序遍歷序列中的第一個元素構造樹的根結點，並將根結點指針入棧。

2）如果棧頂結點的元素值與中序遍歷序列當前處理的元素值不相等，則一直用先序遍歷序列中的元素構造樹結點，如果flag標志值為0，將新結點添加為樹當前處理結點的左孩子結點；否則，添加為右孩子結點。

3）如果棧頂結點的元素值與中序遍歷序列當前處理的元素值相等，則將棧頂結點置為樹的當前處理結點，然後將該結點出棧，並將flag標志置為1.

4）重復2）和3）的操作，直到先序遍歷序列處理完。

用棧來實現構造二叉樹的代碼實現：

TreeNode *buildTree1(vector &preorder, vector &inorder)
{

    if(preorder.size()==0)
        return NULL;

    stack st;
    TreeNode *t, *root;
    int i, j;//i，j分別作為前序和中序遍歷序列的處理指針
    int f;//用於標識是否要新建右結點

    f = i = j = 0;

    root = new TreeNode(preorder[i]);
    st.push(root);
    t = root;
    i++;

    while(i
val == inorder[j])
        {
            t = st.top();
            st.pop();
            f = 1;
            j++;
        }
        else
        {
            //case 2a:f = 0,添加左結點
            if(f == 0)
            {
                t -> left = new TreeNode(preorder[i]);
                t = t -> left;
                st.push(t);
                i++;
            }
            //case 2b：f = 1,添加右結點
            else
            {
                f = 0;
                t -> right = new TreeNode(preorder[i]);
                t = t -> right;
                st.push(t);
                i++;
            }
        }
    }

    return root;
}