题目描述
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
解题思想
第一步:如果数组大小为零的话,说明是空节点了。
第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。
第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点
第四步:切割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组)
第五步:切割后序数组,切成后序左数组和后序右数组
第六步:递归处理左区间和右区间
代码
class Solution {
public:
TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0) return nullptr;
//后续遍历数组最后一个元素,就是当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
//如果就一个节点
if (postorder.size() == 1) return root;
//找到中序遍历的切割点
int index;
for (index = 0; index < inorder.size(); index++) {
if (inorder[index] == rootValue) break;
}
//切割中序数组:左闭右开[0,index)
vector<int> leftInorder(inorder.begin(), inorder.begin() + index);
//[index+1,end)
vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());
//postorder舍弃末尾元素
postorder.resize(postorder.size() - 1);
//切割后续数组:个数 为中序数组的left元素个数就是 和 right元素个数
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) {
return traversal(inorder, postorder);
}
};