106.从中序与后序遍历序列构造二叉树
文章讲解：106.从中序与后序遍历序列构造二叉树
构造二叉树的流程
举一个例子：
中序：9 3 15 20 7
后序：9 15 7 20 3
我们可以从后序中确定根结点是3；那么再切换到中序可知，左区间是9，右区间是15，20，7；再切换回后序9，15，7，20中，9是左子树里面的，15，7，20是右子树的元素；然后再从后序确定中间结点是20；再回到中序，可以确定20的左结点为15，右结点为7.
这样构造出整个二叉树。
总结上述流程，就是首先从后序确定中间结点，然后从中序确定左右子树，再到后序确定子树的中间结点。
在代码中整个过程分为6步：
后序数组为0，返回空结点
后序数组最后一个元素为结点元素
寻找中序数组位置作中序左右区间的切割点
切割中序数组：形成左中序数组 右中序数组
切割后序数组，拿切中序数组形成的左中序数组去切，因为他俩都是一样的：形成左后序 右后序
递归处理左区间后区间
伪代码
- 确定递归函数的参数返回值：返回值是根据中序和后序构造完后的二叉树的根结点。
TreeNode* traversal(inorder, postorder){
}
- 确定递归函数的终止条件：后序数组为0
- 后序数组为0，返回空结点
if (posrorder.size == 0) return nullptr;
- 确定单层递归逻辑：
- 后序数组的最后一个元素为结点元素
rootvalue = postorder[postorder.size - 1];
root = new TreeNode(rootvalue);
if(postorder.size == 1) return root;//如果只有一个结点的情况
- 寻找中序数组位置作切割点
index = 0;
for (index = 0; index < inorder.size; index++){
if (inorder[index] == rootvalue)
break; //这里为啥要break 因为这里我们是根据index来切割，找到index了目的就达到了
}
- 切割中序数组、5. 切后序数组
切中序数组 左中序 右中序
切后序数组 左后序 右后序
// 切割中序数组
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
- 递归处理左区间后区间
root->left = traversal(左中序，左后序);
root->right = traversal(右中序，右后序);
return root;
注意细节
- 在切割区间的时候，一定要注意循环不变量，坚持左闭右开或者左开右必
- 一定要先切中序数组，再切后序数组。这样才能区分出来相互关系。
CPP代码
class Solution {
private:
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 delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};
654.最大二叉树
文章讲解：654.最大二叉树
构造二叉树的流程
选择数组中最大的书，来切割数组，左区间作为左子树，右区间作为右子树，如此循环构造一颗最大二叉树。
比如说数组：3 2 1 6 0 5
6是最大的数，3 2 1是左子树，3又是最大的数作为6的左孩子；2 1是3的右区间作为右子树，2又是最大的作为3的右孩子，1是2的右区间，所以1是2的右孩子，由此得出二叉树
6
/ \
3 5
\ /
2 0
\
1
凡是构造二叉树类的题目一律使用前序遍历，前序遍历是中左右，一定要先构造中，只有构造出根结点才好去构造左子树和右子树。
伪代码
- 确定参数和返回值：参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。
TreeNode* constructMaximumBinaryTree(vector<int>& nums)
- 确定终止条件：当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。
TreeNode* node = new TreeNode(0); //定义新结点
if (nums.size() == 1){
node->val = nums[0];
return node;
}
- 确定单层递归的逻辑
- 先找到数组中最大的值对应的下标，最大的值构造根结点，下标来分割数组
int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < nums.size(); i++){
if (nums[i] > maxValue){
maxValue = nums[i];
maxValueIndex = i;
}
}
TreeNode* node = new TreeNode(0);
node->val = maxValue;
- 最大值所在的下标左区间 构造左子树：判断maxValueIndex > 0要保证左区间至少有一个数值
if (maxValueIndex > 0) {
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
node->left = constructMaximumBinaryTree(newVec);
}
- 最大值所在的下标右区间 构造右子树：判断maxValueIndex < (nums.size() - 1)确保右区间至少有一个数值。
if (maxValueIndex < (nums.size() - 1)) {
vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
node->right = constructMaximumBinaryTree(newVec);
}
CPP代码
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode* node = new TreeNode(0);
if (nums.size() == 1) {
node->val = nums[0];
return node;
}
// 找到数组中最大的值和对应的下标
int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
maxValueIndex = i;
}
}
node->val = maxValue;
// 最大值所在的下标左区间 构造左子树
if (maxValueIndex > 0) {
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
node->left = constructMaximumBinaryTree(newVec);
}
// 最大值所在的下标右区间 构造右子树
if (maxValueIndex < (nums.size() - 1)) {
vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
node->right = constructMaximumBinaryTree(newVec);
}
return node;
}
};
