|
力扣：106.从中序与后序遍历序列构造二叉树
代码随想录
题目：
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
递归思路：
一：通过中序和后序来构建二叉树。
二：先序遍历、找到中间节点，然后分为左树、右树、通过根节点递归构建。
三：代码随想录三步走
1：很明显没有思路，就按2的根、左子树、右子树。然后思考返回值就是节点。通过中序数组、后序数组来构造，可以直接用题目给定的函数形式。
2：此时很明显满足问题的情况不明确。此时就直接分为根的情况，左子树构建，右子树构建。
根的情况：根空、根为叶子
左子树构建：要知道左子树的中序数组和后序数组。
后序数组最后一个即为根，通过根来将中序数组划分为左子树、中、右子树。此时就得到了左子树的中序数组，右子树的中序数组，中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。
通过以上就可以完成左子树的中序数组和后序数组，右子树的中序数组和后序数组。
代码：
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(postorder.size() == 0) return nullptr;
int a = postorder[postorder.size()-1];
TreeNode* node = new TreeNode(a);
if(postorder.size() == 1) return node;
int i;
for (i = 0; i < inorder.size(); ++i){
if(inorder[i] == a) break;
}
vector<int> leftinorder(inorder.begin(), inorder.begin()+i);
vector<int> rightinorder(inorder.begin()+i+1, inorder.end());
postorder.resize(postorder.size()-1);
vector<int>leftpostorder(postorder.begin(), postorder.begin()+leftinorder.size());
vector<int>rightpostorder(postorder.begin()+leftinorder.size(), postorder.end());
node->left = buildTree(leftinorder,leftpostorder);
node->right = buildTree(rightinorder,rightpostorder);
return node;
}
};
注意这个postorder.end()代表的并不是最后一个元素，代表的是最后一个元素的后一位。
同时这个 vector 构造函数是前闭后开的
vector<int>rightpostorder(postorder.begin()+leftinorder.size(), postorder.end());
思考后序数组 （等），将后序数组分为三块：左树、右树、中。想树时也是一个节点两棵树。
后序数组：
左树 右树 中
@@@@———@@@————@
中序数组：
左树 中 右树
@@@@————@————@@@
|