【劍指Offer】重建二叉樹（遞歸+疊代）

重建二叉樹

• 一、遞歸法
• 二、疊代法

題目連結

題目描述：

輸入某二叉樹的前序周遊和中序周遊的結果，請建構該二叉樹并傳回其根節點。

假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]

Output: [-1]

一、遞歸法

首先我們知道中序的左邊就是該節點的左子樹，中序的右邊就是該節點的右子樹，而确認根的順序就需要靠前序。

是以我們可以用一個變量pi記錄前序周遊的位置，在中序中找到相同的元素，然後把它的左右區間遞歸下去。

這裡注意如果要每次遞歸都需要周遊中序找到根，時間複雜度過高，是以我們可以在遞歸前先用哈希表映射根的位置。

代碼如下

class Solution {
public:
    unordered_map<int, int> index;

    TreeNode* _bulidTree(vector<int>& pre, vector<int>& in, int& pi, int begin, int end)
    {
        if (begin > end) return nullptr;
        int mid = index[pre[pi]];
        TreeNode* root = new TreeNode(pre[pi++]);
        root->left = _bulidTree(pre, in, pi, begin, mid - 1);
        root->right = _bulidTree(pre, in, pi, mid + 1, end);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pi = 0;
        for (int i = 0; i < preorder.size(); i++)
        {
            index[inorder[i]] = i;
        }
        return _bulidTree(preorder, inorder, pi, 0, preorder.size() - 1);
    }
};
           

二、疊代法

三種順序的疊代法周遊：【資料結構】二叉樹的非遞歸周遊

我們先假象一種情況，一棵樹隻有左子樹的話，那麼就相當于是一個單連結清單，那麼它的前序周遊和中序周遊就剛好是反過來的。那麼我們就可以使用棧來逆序存放，一旦周遊到最左下節點，這時候就該傳回，開始彈棧，當我們發現彈棧的順序和中序周遊不一緻的時候，說明最後一個彈出來的節點有右子樹。

可以發現前序走完後出棧順序剛好是中序周遊的結果，是以沒有右子樹。

代碼如下：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return nullptr;
        stack<TreeNode*> st;
        int inorIndex = 0;
        TreeNode* root = new TreeNode(preorder[0]);
        st.push(root);
        for(int i = 1; i < preorder.size(); i++)
        {
            TreeNode* node = st.top();
            if(node->val != inorder[inorIndex])
            {
                node->left = new TreeNode(preorder[i]);
                st.push(node->left);
            }
            else
            {
                while(!st.empty() && st.top()->val == inorder[inorIndex])
                {
                    node = st.top();
                    st.pop();
                    inorIndex++;
                }
                node->right = new TreeNode(preorder[i]);
                st.push(node->right);
            }
        }
        return root;
    }
};