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

力扣题目链接

文章讲解：106.从中序与后序遍历序列构造二叉树

视频讲解：坑很多！来看看你掉过几次坑 | LeetCode：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步：

1. 后序数组为0，返回空结点

2. 后序数组最后一个元素为结点元素

3. 寻找中序数组位置作中序左右区间的切割点

4. 切割中序数组：形成左中序数组 右中序数组

5. 切割后序数组，拿切中序数组形成的左中序数组去切，因为他俩都是一样的：形成左后序 右后序

6. 递归处理左区间后区间

伪代码

• 确定递归函数的参数返回值：返回值是根据中序和后序构造完后的二叉树的根结点。

TreeNode* traversal(inorder, postorder){}

• 确定递归函数的终止条件：后序数组为0

1. 后序数组为0，返回空结点

if (posrorder.size == 0) return nullptr;

• 确定单层递归逻辑：

2. 后序数组的最后一个元素为结点元素

rootvalue = postorder[postorder.size - 1];
root = new TreeNode(rootvalue);
if(postorder.size == 1) return root;//如果只有一个结点的情况

3. 寻找中序数组位置作切割点

index = 0;
for (index = 0; index < inorder.size; index++){if (inorder[index] == rootvalue)break;	//这里为啥要break 因为这里我们是根据index来切割，找到index了目的就达到了
}

4. 切割中序数组、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());

6. 递归处理左区间后区间

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.最大二叉树

视频讲解：又是构造二叉树，又有很多坑！| LeetCode：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;
}

• 确定单层递归的逻辑

1. 先找到数组中最大的值对应的下标，最大的值构造根结点，下标来分割数组

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;

2. 最大值所在的下标左区间 构造左子树：判断maxValueIndex > 0要保证左区间至少有一个数值

if (maxValueIndex > 0) {vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);node->left = constructMaximumBinaryTree(newVec);
}

3. 最大值所在的下标右区间 构造右子树：判断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;}
};