从中序与后序遍历序列构造二叉树

力扣题目链接

题目描述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

解题思路

这道题很有难度，如果是从中序后序遍历去构造二叉树，还是很简单的，但是用代码取实现在思路上就很绕。

首先我们先来解决如何构造这个二叉树的逻辑：

• 对于给定中序和后序遍历或者前序和中序遍历序列构造二叉树，最重要的是这个中序遍历序列，因为中序可以分割二叉树的左右子树；
• 那么这里我们需要的是后序序列先确定该序列的根节点，然后在中序序列中去寻找这个节点，然后分割出左右子树；
• 根据分割的左右序列的长度，我们可以确定后序遍历序列的左右子树位置及长度；
• 把这些分割好的左右子树的中序和后序序列传入函数重复上述的操作即可。

上述思路如果不理解可以先去自行搜索二叉树相关的文章学习二叉树的基本知识。
在代码书写上，我们需要注意以下几点：

• 递归的使用最重要的就是，我们确定好函数的传入参数以及返回值，这里我们需要的就是中序和后序的序列作为参数，对于每个子树的构造来说都是足够的。而返回值的选择自然是一个树节点的指针，用于返回该节点作为根节点的子树；
• 合理分割遍历序列，才能保证子树的正确构造。在这里我们需要把序列根据左右子树给分割开，那么我们就需要声明几个新的数组变量来分别存储左右子树的中后序列然后传入函数，接受作为子树；

题解

class Solution {TreeNode* func(vector<int>& inorder, vector<int>& postorder){if(postorder.size() == 0){return NULL;}int num = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(num);if(postorder.size() == 1){return root;}int p1;for(p1 = 0; p1 < postorder.size(); p1++){if(inorder[p1] == num) {break;}}vector<int> leftInorder(inorder.begin(), inorder.begin() + p1);vector<int> rightInorder(inorder.begin() + p1 + 1, inorder.end());postorder.resize(postorder.size() - 1);vector<int> leftPostorder(postorder.begin(), postorder.begin() + p1);vector<int> rightPostorder(postorder.begin() + p1, postorder.end());root->left = func(leftInorder, leftPostorder);root->right = func(rightInorder, rightPostorder);return root; } public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size() == 0 || postorder.size() == 0){return NULL;}return func(inorder, postorder);}
};

总结

这道题目在思路上不难想到，主要是对于分割序列的左右边界需要多加留意。