由前/中/后遍歷序列構建二叉樹

看一下前序和中序有什么特點，前序1,2,4,7,3,5,6,8 ，中序4,7,2,1,5,3,8,6；

當前要構造的樹（可能是整體的某個子樹）所需的前序/中序遍歷序列肯定是整體所求樹的前序/中序遍歷序列的某個子序列，我們用 preLeft, preRight, inLeft, inRight 分別表示該子序列在整體前序/中序序列中的起始位置。

1. 前序中左起第一位1肯定是根結點 root，我們可以根據其值 rootVal 找到中序中根結點的位置記為 mid；
2. 中序中根結點左邊就是左子樹結點，右邊就是右子樹結點。即[左子樹結點，根結點，右子樹結點]，我們就可以得出左子樹結點個數為 mid-inLeft；
3. 前序中結點分布應該是：[根結點，左子樹結點，右子樹結點]；
4. 根據前一步確定的左子樹個數，可以確定前序中左子樹結點和右子樹結點的范圍；
5. 如果我們要前序遍歷生成二叉樹的話，下一層遞歸應該是：
   • 左子樹：root->left = helper(preorder, inorder, 左子樹前序起始點, 左子樹前序終止點, 左子樹中序起始點, 左子樹中序終止點);
   • 右子樹：root->right = helper(preorder, inorder, 右子樹前序起始點, 右子樹前序終止點, 右子樹中序起始點, 右子樹中序終止點);
6. 每一層遞歸都要返回當前根結點root；

全部代碼如下：

class Solution {
private:TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int preLeft, int preRight, int inLeft, int inRight) {if (inLeft >= inRight) return nullptr;int rootVal = preorder[preLeft];int mid = inLeft;for (; mid<inRight; ++mid) if (inorder[mid] == rootVal) break;TreeNode* root = new TreeNode(rootVal);root->left = helper(preorder, inorder, preLeft+1, preLeft+1+mid-inLeft, inLeft, mid);root->right = helper(preorder, inorder, preLeft+1+mid-inLeft, preRight, mid+1, inRight);return root;}
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return helper(preorder, inorder, 0, preorder.size(), 0, inorder.size());}
};

與前序中序構造二叉樹類似：

class Solution {
private:TreeNode* helper(vector<int>& inorder, vector<int>& postorder, int inLeft, int inRight, int postLeft, int postRight) {if (inLeft >= inRight) return nullptr;int rootVal = postorder[postRight-1];int mid = inLeft;for (; mid<inRight; ++mid) if (inorder[mid] == rootVal) break;TreeNode* root = new TreeNode(rootVal);root->left = helper(inorder, postorder, inLeft, mid, postLeft, postLeft+mid-inLeft);root->right = helper(inorder, postorder, mid+1, inRight, postLeft+mid-inLeft, postRight-1);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return helper(inorder, postorder, 0, inorder.size(), 0, postorder.size());}
};

注意，我們之前提到前序/后序序列并不能唯一確定一棵二叉樹（實際上，只有每個節點度為2或者0的時候前序和后序才能唯一確定一顆二叉樹），所以本題題目說明中有：

• 每個輸入保證至少有一個答案。如果有多個答案，可以返回其中一個。

class Solution {
private:TreeNode* helper(vector<int>& preorder, vector<int>& postorder, int preLeft, int preRight, int postLeft, int postRight) {if (preLeft > preRight) return nullptr;int rootVal = preorder[preLeft];TreeNode* root = new TreeNode(rootVal);if (preLeft == preRight) return root;int mid = 0;for (; mid<postRight; ++mid) if (postorder[mid] == preorder[preLeft+1]) break;root->left = helper(preorder, postorder, preLeft+1, preLeft+1+mid-postLeft, postLeft, mid);root->right = helper(preorder, postorder, preLeft+2+mid-postLeft, preRight, mid+1, postRight-1);return root;}
public:TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {return helper(preorder, postorder, 0, preorder.size()-1, 0, postorder.size()-1);}
};