题目描述
给定两个整数数组 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.使用索引来代替新建数组会更省时间。