程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 通過二叉樹的中序和後序遍歷序列構造二叉樹(非遞歸)

通過二叉樹的中序和後序遍歷序列構造二叉樹(非遞歸)

編輯:C++入門知識

題目:通過二叉樹的中序和後序遍歷序列構造二叉樹

同樣,使用分治法來實現是完全可以的,可是在LeetCode中運行這種方法的代碼,總是會報錯:

Memory Limit Exceeded

,所以這裡還是用棧來實現二叉樹的構建。

與用先序和後序遍歷構造二叉樹的方法類似,但還是要做一些改變:

\

\\

如果從後往前處理中序和後序的序列,則處理就為如下所示的情況:

Reverse_PZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3Q6ILj5oarT0tfTyvehqtfz19PK9zxicj4KUmV2ZXJzZV9Jbjog09LX08r3oaq4+aGq1/PX08r3PC9wPgo8cD48L3A+CjxpbWcgc3JjPQ=="" alt="\">
這樣處理方式和先序—中序就差不多了,只是將添加左孩子的情況,改為添加右孩子,反之依然。 實現代碼如下所示:

TreeNode *buildTree_in_post(vector &inorder, vector &postorder)
{
    stack s;
    int len = (int) inorder.size();
    if(len == 0)
        return  NULL;
    int in_ptr, post_ptr;//分別用於對中序和後序處理
    in_ptr = post_ptr = len-1;//從序列最後一個元素往前進行處理
    TreeNode* root = new TreeNode(postorder[post_ptr]);//構造根結點,後序遍歷最後一個元素為根結點的值
    TreeNode* pCur = root;//用於保存樹當前處理結點
    int flag = 0;//用於決定是否構造左結點
    post_ptr--;
    s.push(root);

    while(post_ptr > -1)//處理到pOstorder[0]
    {
        if(!s.empty() && s.top()->val == inorder[in_ptr])
        {
           pCur = s.top();
           s.pop();
           in_ptr--;
           flag = 1;
        }
        else
        {
            if(flag == 1)//構造左結點
            {
                pCur->left = new TreeNode(postorder[post_ptr]);
                pCur = pCur->left;
                s.push(pCur);
                post_ptr--;
                flag = 0;
            }
            else//構造右結點
            {
                pCur->right = new TreeNode(postorder[post_ptr]);
                pCur = pCur->right;
                s.push(pCur);
                post_ptr--;
            }
        }
    }
    return root;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved