无锡网站推,百度的网址是什么呢,电商平台需要什么资质,网站招生宣传怎么做力扣日记#xff1a;【二叉树篇】从中序与后序遍历序列构造二叉树 日期#xff1a;2023.12.13 参考#xff1a;代码随想录、力扣 106. 从中序与后序遍历序列构造二叉树
题目描述 难度#xff1a;中等 给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder 是二…力扣日记【二叉树篇】从中序与后序遍历序列构造二叉树 日期2023.12.13 参考代码随想录、力扣 106. 从中序与后序遍历序列构造二叉树
题目描述 难度中等 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。
示例 1: 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3] 输出[3,9,20,null,null,15,7] 示例 2: 输入inorder [-1], postorder [-1] 输出[-1] 提示:
1 inorder.length 3000postorder.length inorder.length-3000 inorder[i], postorder[i] 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历
题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
# define SOLUTION 2
public:
# if SOLUTION 1TreeNode* buildTree(vectorint inorder, vectorint postorder) {// 递归返回值与参数返回值为中节点, 参数为中序和后序数组// 从中序与后序遍历序列构造二叉树的步骤// 1. 如果后序数组为空, 则为空节点(终止条件)if (postorder.size() 0) return nullptr; // 为空节点// 2. 根据后序数组最后一个值得到中节点值int nodeVal postorder[postorder.size() - 1]; // 后序数组最后一个值为中节点值TreeNode* node new TreeNode(nodeVal); // 构造中节点// 注意如果是叶子节点, 则不需要再去切割, 直接返回当前节点if (postorder.size() 1) return node;// 3. 寻找中序数组位置作切割点int index 0;for (int i 0; i inorder.size(); i) {if (inorder[i] nodeVal) {index i; // index 为中节点值对应序号, 则[0, index)为左子树, [index 1, size)为右子树, 注意统一区间开闭 }}// 4. 根据此切割点对中序数组进行切割vectorint inorderLeft(inorder.begin(), inorder.begin() index); // [0, index)vectorint inorderRight(inorder.begin() index 1, inorder.end()); // [index 1, size)// 5. 再根据切割后中序数组左右区间长度对后序数组进行切割vectorint postorderLeft(postorder.begin(), postorder.begin() inorderLeft.size()); // [0, left.size)vectorint postorderRight(postorder.begin() inorderLeft.size(), postorder.begin() inorderLeft.size() inorderRight.size()); // [left.size, left.size right.size)// 6. 将中序数组与后序数组的左子树区间进行递归处理, 递归返回值为左子树的根节点,作为当前node左节点node-left buildTree(inorderLeft, postorderLeft); // 中序和后序的左子树遍历数组都分别按中序和后序遍历// 7. 将中序数组与后序数组的右子树区间进行递归处理node-right buildTree(inorderRight, postorderRight);return node; // 返回已经接上左右节点的中节点}
# elif SOLUTION 2 // 优化用下标索引不需要每次构建子数组TreeNode* buildTree(vectorint inorder, vectorint postorder) {int inorderBegin 0, inorderEnd inorder.size(); // [0, size)int postorderBegin 0, postorderEnd postorder.size(); // [0, size)return traversal(inorder, inorderBegin, inorderEnd, postorder, postorderBegin, postorderEnd);}TreeNode* traversal (vectorint inorder, int inorderBegin, int inorderEnd, vectorint postorder, int postorderBegin, int postorderEnd) {// 递归返回值与参数返回值为中节点, 参数为原始中序后序数组, 以及用来表示当前中后序数组的下标// 不变量左闭右开// 从中序与后序遍历序列构造二叉树的步骤// 1. 如果当前后序数组为空, 则为空节点(终止条件)if (postorderEnd - postorderBegin 0) return nullptr; // 为空节点 [Begin, Begin)// 2. 根据后序数组最后一个值得到中节点值int nodeVal postorder[postorderEnd - 1]; // 后序数组最后一个值为中节点值, 右开, 则需-1TreeNode* node new TreeNode(nodeVal); // 构造中节点// 注意如果是叶子节点, 则不需要再去切割, 直接返回当前节点if (postorderEnd - postorderBegin 1) return node;// 3. 寻找中序数组位置作切割点int index 0;for (int i inorderBegin; i inorderEnd; i) {if (inorder[i] nodeVal) {index i; // index 为中节点值对应序号, 则[inorderBegin, index)为左子树, [index 1, inorderEnd)为右子树, 注意统一区间开闭 }}// 4. 根据此切割点对中序数组进行切割int inorderLeftBegin inorderBegin; // 左子树区间的开始下标(左闭)int inorderLeftEnd index; // 左子树区间的结束下标(右开)int inorderRightBegin index 1; // 右子树区间int inorderRightEnd inorderEnd;// 5. 再根据切割后中序数组左右区间长度对后序数组进行切割int LeftSize inorderLeftEnd - inorderLeftBegin; // 左子树大小int postorderLeftBegin postorderBegin;int postorderLeftEnd postorderBegin LeftSize; // 后序与中序的左子树数组大小一致, LeftSize: [postorderLeftBegin, postorderLeftBegin LeftSize)int RightSize inorderRightEnd - inorderRightBegin;int postorderRightBegin postorderLeftEnd; // 左闭int postorderRightEnd postorderLeftEnd RightSize;// 6. 将中序数组与后序数组的左子树区间进行递归处理, 递归返回值为左子树的根节点,作为当前node左节点node-left traversal(inorder, inorderLeftBegin, inorderLeftEnd, postorder, postorderLeftBegin, postorderLeftEnd); // 中序和后序的左子树遍历数组都分别按中序和后序遍历// 7. 将中序数组与后序数组的右子树区间进行递归处理node-right traversal(inorder, inorderRightBegin, inorderRightEnd, postorder, postorderRightBegin, postorderRightEnd);return node; // 返回已经接上左右节点的中节点}
# endif
};复杂度
时间复杂度 空间复杂度
思路总结
从中序与后序遍历序列构造二叉树的步骤 如果后序数组为空, 则为空节点根据后序数组最后一个值得到中节点值寻找中序数组位置作切割点根据此切割点对中序数组进行切割再根据切割后中序数组左右区间长度对后序数组进行切割将中序数组与后序数组的左子树区间进行递归处理(两个左子树区间数组分别为左子树的中序数组和后序数组)将中序数组与后序数组的右子树区间进行递归处理 示意图 对于第二种解法即用下标索引表示子数组而不是直接构造子数组要分别确定好左右子树的中序和后序数组的开始、结束下标。统一用左闭右开来表示。相对繁琐一些但时间和空间复杂度更优化。
相关题目105. 从前序与中序遍历序列构造二叉树
题目描述 难度中等 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] 示例 2: 输入: preorder [-1], inorder [-1] 输出: [-1] 提示:
1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder 和 inorder 均 无重复 元素inorder 均出现在 preorderpreorder 保证 为二叉树的前序遍历序列inorder 保证 为二叉树的中序遍历序列
题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {// 1. 如果前序数组为空, 则为空节点if (preorder.size() 0) return nullptr;// 2. 根据前序数组第一个值得到中节点值int nodeVal preorder[0];// 构造中节点TreeNode* node new TreeNode(nodeVal);// 如果是叶子节点直接返回if (preorder.size() 1) return node;// 3. 寻找中序数组位置作切割点int index 0;for (int i 0; i inorder.size(); i) {if (inorder[i] nodeVal) {index i;}}// 4. 根据此切割点对中序数组进行切割vectorint inorderLeft(inorder.begin(), inorder.begin() index);vectorint inorderRight(inorder.begin() index 1, inorder.end());// 5. 再根据切割后的中序数组左右区间长度对前序数组进行切割vectorint preorderLeft(preorder.begin() 1, preorder.begin() 1 inorderLeft.size()); // 第二个值开始vectorint preorderRight(preorder.begin() 1 inorderLeft.size(), preorder.end());// 6. 将中序数组与前序数组的左子树区间进行递归处理(两个左子树区间数组分别为左子树的中序数组和前序数组)node-left buildTree(preorderLeft, inorderLeft);// 7. 将中序数组与前序数组的右子树区间进行递归处理node-right buildTree(preorderRight, inorderRight);return node;}
};复杂度
思路总结
与 从后序与中序遍历序列构造二叉树 的思路基本一致从前序与中序遍历序列构造二叉树的步骤前序中左右中序左中右 如果前序数组为空, 则为空节点根据前序数组第一个值得到中节点值寻找中序数组位置作切割点根据此切割点对中序数组进行切割再根据切割后的中序数组左右区间长度对前序数组进行切割将中序数组与前序数组的左子树区间进行递归处理(两个左子树区间数组分别为左子树的中序数组和前序数组)将中序数组与前序数组的右子树区间进行递归处理 这里要明确一点前序和中序、后序和中序都可以分别唯一确定一棵二叉树但前序和后序不能唯一确定一棵二叉树因为没有中序遍历无法确定左右部分也就是无法分割。 如上面两棵树的前序、后序都分别相等
