# [ 二叉树 ] 中序和后序遍历确定二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)

# 中序和后序遍历确定二叉树

## 递归

• 明确：分治
• 左闭右开切割
``````class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 构造返回值
TreeNode* root = new TreeNode();

// 空组返回
if (postorder.empty()) return nullptr;

// 寻找中序切割点， 也同样为根节点
int cutPointValue = postorder[postorder.size() - 1];
root->val = cutPointValue;

// 如果只剩一个根结点直接返回即可
if (postorder.size() == 1) return root;

// 否则切割
int inCutPoint = 0;
for (; inCutPoint < inorder.size(); ++inCutPoint)
if (cutPointValue == inorder[inCutPoint]) break;

// 左闭右开原则
vector<int> inLeft(inorder.begin(), inorder.begin() + inCutPoint);
vector<int> inRight(inorder.begin() + inCutPoint + 1, inorder.end());

int postCutPoint = inLeft.size();
vector<int> postLeft(postorder.begin(), postorder.begin() + postCutPoint);
vector<int> postRight(postorder.begin() + postCutPoint, postorder.end() - 1);

root->left = buildTree(inLeft, postLeft);
root->right = buildTree(inRight, postRight);

return root;
}
};
``````
• 空间优化 利用下标代替切割
• 如果每次切割都创造新向量则会产生过多的空间开销
``````class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}

TreeNode* traversal(vector<int> &inorder, int inBegin, int inEnd,
vector<int> &postOrder, int postBegin, int postEnd) {
if (postBegin == postEnd) return nullptr;

int rootValue = postOrder[postEnd - 1];
TreeNode* root = new TreeNode(rootValue);

if (postBegin == postEnd - 1) return root;

int inCut = 0;
for (; inCut < inEnd; ++inCut) {
if (inorder[inCut] == rootValue) break;
}

// 传递下标代替切割
int leftInBegin = inBegin;
int leftInEnd = inCut;
int rightInBegin = inCut + 1;
int rightInEnd = inEnd;
int leftPostBegin = postBegin;
int leftPostEnd = postBegin + leftInEnd - leftInBegin;
int rightPostBegin = leftPostEnd;
int rightPostEnd = postEnd - 1;

root->left = traversal(inorder, leftInBegin, leftInEnd, postOrder, leftPostBegin, leftPostEnd);
root->right = traversal(inorder, rightInBegin, rightInEnd, postOrder, rightPostBegin, rightPostEnd);
return root;
}
};
``````