题目描述
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
思路
递归法
递归法步骤：
第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间
代码
C++版：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){
// 第一步，判断是否为空节点
if(postorder.size()==0) return NULL;
// 第二步，取后序数组最后一个元素作为节点元素
int rootValue=postorder[postorder.size()-1];
TreeNode* root=new TreeNode(rootValue);
// 仅有一个节点
if(postorder.size()==1) return root;
// 第三步，找切割点
int i;
for(i=0;i<inorder.size();i++){
if(inorder[i]==rootValue) break;
}
// 第四步，切割中序数组，得到中序左数组[0, i)和中序右数组[i+1,end)，
vector<int> leftInorder(inorder.begin(),inorder.begin() + i);
vector<int> rightInorder(inorder.begin()+i+1,inorder.end());
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 第五步，切割后序数组，得到后序左数组和后序右数组
vector<int> leftPostorder(postorder.begin(), postorder.begin()+leftInorder.size());
vector<int> rightPostorder(postorder.begin()+leftInorder.size(), postorder.end());
// 第六步，递归处理左区间和右区间
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size()==0 || postorder.size()==0) return NULL;
return traversal(inorder,postorder);
}
};Python版：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
# 第一步: 特殊情况讨论: 树为空. (递归终止条件)
if not postorder:
return None
# 第二步: 后序遍历的最后一个就是当前的中间节点.
root_val = postorder[-1]
root = TreeNode(root_val)
# 第三步: 找切割点.
separator_idx = inorder.index(root_val)
# 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
inorder_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
# 第五步: 切割postorder数组. 得到postorder数组的左,右半边.
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left): len(postorder) - 1]
# 第六步: 递归
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
return root需要注意的地方
1.由于中序数组大小一定是和后序数组的大小相同的，将中序数组切成了左中序数组和右中序数组后，后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。
2.使用索引来代替新建数组会更省时间。