題目：重建二叉樹

題目描述：

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字馆里。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}染坯，則重建二叉樹并返回。

題目知識：

首先看題目應該最先看到的是這個幾個關(guān)鍵點：1揽碘、二叉樹，2园匹、二叉樹的前中后三種遍歷雳刺。
先序遍歷：遍歷規(guī)則 根-左-右
中序遍歷：遍歷規(guī)則 左-根-右
后序遍歷：遍歷規(guī)則 左-右-根

image.png

題目分析

已知當知道先序和中序遍歷的序列，或者知道中序和后序遍歷序列時我們可以唯一確定一個二叉樹允蚣，當只知道先序和后序的時候我們不能確定唯一的一棵樹于颖。
那我們先聯(lián)系這樣一個題目：
已知先序序列：ABCDEFGH,中序序列：BDCEAFHG,求出最終的序列來。
首先嚷兔，先序和中序的遍歷規(guī)則分別是根左右和左根右,那么我們可以知道此序列的根節(jié)點是A森渐，在中序序列中，BDCE是A的左子樹冒晰，F(xiàn)HG是A的右子樹同衣。

image.png

image.png

image.png

image.png

我們同樣對右子樹進行操作辕翰，在先序中右子樹的順序是：FGH，那么此右子樹的根節(jié)點是F浙巫，再看中序的順序是：FHG金蜀，F(xiàn)是根節(jié)點，那HG是F的右子樹

image.png

image.png

接下來
我們知道中序遍歷：CEDFBAHG护桦，后序遍歷：EFDCBHGA
我們知道：
1、根據(jù)后序遍歷知道此二叉樹的根節(jié)點是A煎娇，那么在中序遍歷中我們就可以分成左子樹：CEDFB二庵，右子樹HG贪染。
2、先看左子樹的后序：EFDCB催享，我們知道左子樹的根節(jié)點是B杭隙，再到中序CEDFB中我們知道。CEDF是B的左子樹因妙。
3痰憎、后序：EFDC，知道B的左子樹的根節(jié)點是C攀涵，铣耘，而在中序CEDF中我們知道EDF是C的右子樹
4、后序：EFD以故，知道C的右子樹的根節(jié)點是D蜗细，而在中序EDF中我們知道E和F分別是D的左葉子節(jié)點和有葉子結(jié)點
5、中序：HG怒详，我們知道是A的右子樹炉媒，后序中HGA，說明A的右子樹的根節(jié)點是G昆烁。
6橱野、中序遍歷中是HG，說明H是G的左葉子節(jié)點

image.png

綜上所述善玫，我們可以知道從遍歷中獲取整個二叉樹的方法

題目代碼：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() != vin.size()||pre.size() == 0 || vin.size() == 0) return NULL;
        else{
            TreeNode* resNode = createTreeNodeHelper(pre,vin,0,0,vin.size()-1);
            return resNode;
        }
    }
    TreeNode* createTreeNodeHelper(vector<int> pre, vector<int> vin,int preRootPos,int vinLeft,int vinRight){
        // pre 前序 vin 中序 preRootPos 前序根節(jié)點位置 vinLeft 中序左邊界 vinRight 中序右邊界
        int vinRootPos,rootVal;
        rootVal = pre[preRootPos];//前序遍歷中根節(jié)點位置的值
        if(vinLeft>vinRight) return NULL;
        for(int i = vinLeft; i<=vinRight;i++){
            if(vin[i] == rootVal)
                vinRootPos = i; //根據(jù)根節(jié)點找到中序中根節(jié)點的位置vinRootPos,
        }
        int leftLen = vinRootPos - vinLeft;
        
        TreeNode* resRoot = new TreeNode(rootVal);
        resRoot->left = createTreeNodeHelper(pre,vin,preRootPos+1,vinLeft,vinRootPos-1);
        resRoot->right = createTreeNodeHelper(pre,vin,preRootPos+leftLen+1,vinRootPos + 1, vinRight);
        return resRoot;
    }
};

通過迭代的方式，不斷查找密强。