猜你喜歡：
【演算法入門】最短時間學會DFS深度優先搜索

前言

首先來回憶一下三種遍歷方式，前序遍歷：根左右，中序遍歷：左根右，后序遍歷：左右根，

【建議收藏】

一、從中序與后序遍歷序列構造二叉樹

首先說明，這三道題萬變不離其中，我們在這里都用遞回的方式去求解，我個人認為這道題比較典型，我們在這里就先講述這題
從中序與后序遍歷序列構造二叉樹

題目很短，要如何做呢，如果我們先不用代碼做，我們通過畫圖的方式先理解一下例如，給出

中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]

分析：
我們首先找比較好確定的，這顆樹的根肯定是很明顯的了，后序遍歷的最后一個（postend），這個肯定是跑不了了，那我們我們有了根，只需要去遞回構建根的左子樹和右子樹了，那么應該怎么做呢？
答案：我們通過遍歷中序區間就可以找到左子樹的區間和右子樹的區間！
這句話非常重要！！！我們能從左子樹拿到左子樹的中序區間，想要構建左子樹也是不夠的，不信你自己拿著左區間弄一個左子樹試試，那我們這里有了左子樹的區間，我們同時知道后序遍歷實作遞回構建左子樹的，那么我們這里就等于找到了中序遍歷和后序遍歷的左子樹區間！！！！
看到這里有沒有感覺到我們將問題給子問題，那么拿著中序遍歷和后序遍歷的左子樹區間又要怎么做呢？我們是不是看看能否繼續拆分子區間，然后等到區間只有一個值的時候說明他已經走到中序區間的最左端了，相當于你走中序遍歷的時候走到 “南墻” 了，如圖：當中序遍歷和后序遍歷的左區間只有一個值時，不可以再拆分了，此時他就是一個轉折點，
root為當前區間的根！
root為當前區間的根！
root為當前區間的根！（左區間也好，右區間也一樣！！）

class Solution {
public:
TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int ini, int inend, int posti, int postend)
{
	//當區間中存在一個值的情況都需要進來，當不存在的時候直接回傳
    if (ini > inend || posti > postend)
        return NULL;
        
        //用后序遍歷的最后一個元素（根）創造頭結點
        //每次進來創建頭結點，鏈接左子樹和右子樹，注意這里的root就是當前區間的根
    TreeNode* root = new TreeNode(postorder[postend]);
    
	//對區間至少為2的才考慮
    if (ini + 1 <= inend)
    {
     //[ini,index-1]index[index+1,inend]中序區間
     //[posti,posti+cut][posti+cut+1,postend-1]postend后序區間
        int index = ini;
        while (inorder[index] != postorder[postend])
        {
            index++;
        }
        //左子樹的節點數
        int cut = index - ini ;

        root->left = _buildTree(inorder, postorder, ini, index - 1, posti, posti + cut-1 );

        root->right = _buildTree(inorder, postorder, index+1, inend, posti + cut, postend - 1);

       
    }
	//區間為一的情況或者最后回傳都是回傳當前創造的節點
    return root;

}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    return _buildTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
};

二、 從前序與中序遍歷序列構造二叉樹

從前序與中序遍歷序列構造二叉樹

倘若上道題沒有聽懂也無妨，這道題對于上題懂了的同學實際是更加方便解決的，
分析：前序遍歷和中序遍歷，我們同樣可以將兩種遍歷分別區分左區間和右區間，然后再通過這兩個區間再遞回往下走，實際上就這樣就可以了
當然我這里甚至可以用一個prei（前序遍歷的指標）走就可以，因為我們每次剛好拿到的都是根，就不用向上題那樣確定兩個遍歷序列的區間在去找根，

class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,
        int& prei, int ini, int inend)
    {
        //拿preorder[prei]來建根
        TreeNode* root = new TreeNode(preorder[prei]);

        int index = ini;
        while (preorder[prei] != inorder[index])
        {
            index++;
        }
        //中序[ini,index-1]index[index+1,inend]
        if (ini <= index - 1)
        {
            //表示左區間存在
            root->left = _buildTree(preorder, inorder, ++prei , ini, index - 1);
        }
        else
            root->left = NULL;
		
		//表示右區間存在
        if (index + 1 <= inend)
        {
            root->right = _buildTree(preorder, inorder, ++prei, index + 1, inend);
        }
        else
            root->right = NULL;
		//最后回傳根
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};

三、根據前序和后序遍歷構造二叉樹

根據前序和后序遍歷構造二叉樹

首先這題說明一下，這道題是有多種答案的，我們只需要回傳其中一種，
我們的解法也是和上題一樣，找到前序遍歷和后序遍歷的左區間和右區間，然后遞回構建左子樹和右子樹，

大家可以嘗試自己寫一寫，再對一下下面的答案！！

class Solution {
public:
    TreeNode* _constructFromPrePost(vector<int>& preorder, vector<int>& postorder,
        int prei, int preend, int posti, int postend)
    {
        //相等的時候說明都還有一個節點可以創建
        if (prei > preend || posti > postend)
            return NULL;
        int val = preorder[prei];
        TreeNode* root = new TreeNode(val);

        //記錄左子樹的節點個數
        int postbegin = posti;
        //當后序遍歷的頭尾指向不是同一個的時候說明還可以進行拆分
        if (posti+1<=postend)
        {
            while (postbegin <= postend)
            {
                if (postorder[postbegin] == preorder[prei + 1])
                {
                    break;
                }
                else
                    postbegin++;
            }
            int cut = postbegin - posti + 1;//左子樹的節點個數
        //劃磁區間
        //左區間[prei+1,prei+cut]   [posti, posti+cut-1]
        //右區間 [previ+cut+1,preeend] [posti+cut,postend-1] 
            root->left = _constructFromPrePost(preorder, postorder, prei + 1, prei + cut, posti, posti + cut - 1);
            root->right = _constructFromPrePost(preorder, postorder, prei + cut + 1, preend, posti + cut, postend - 1);
        }
        //走到這里說明區間只有一個節點，直接回傳給上層即可
        //只有一個節點就直接回傳節點
        return root;
    }
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        return  _constructFromPrePost(preorder, postorder, 0, preorder.size() - 1, 0, postorder.size() - 1);
    }
};

總結

任意兩種遍歷序列構造二叉樹的寫法這章只寫了用遞回邏輯去完成，實際上也有用迭代的一些比較巧的方法，大家感興趣也可以了解了解！！
看到這里不妨給個一鍵三連！！