二叉树的构造类问题
1.这类问题主要是从已有数组里面构造二叉树
2.主要思想是按照要求找到根节点, 然后以某种形式递归地构建左右子树
654.最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。示例 1：输入：nums = [3,2,1,6,0,5] 输出：[6,3,5,null,2,0,null,null,1] 解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
示例 2：输入：nums = [3,2,1] 输出：[3,null,2,null,1]
分析:
1.直接按照规则扫描数组拿到最大值, 然后递归构造左右子树, 伪代码思路如下:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if (nums.empty()) {
return nullptr;
}
int maxIdx = 0;
int maxValue = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > maxValue) {
maxIdx = i;
maxValue = nums[i];
}
}
TreeNode* root = new TreeNode(maxValue);
root->left = constructMaximumBinaryTree(nums[0..maxIdx-1]); // 每次递归的时候这里的数组索引需要更新
root->right = constructMaximumBinaryTree(nums[maxIdx+1..nums.size()-1]); // 每次递归的时候这里的数组索引需要更新
return root;
}
每次递归构建左右子树的时候, 需要的数组索引区间都是在变更的, 因此需要引入一个辅助函数, 去每次递归的时候带上构建子树对应的数组内索引的起点和终点
完整答案如下
class Solution {
public:
TreeNode* build(vector<int>& nums, int low, int high) {
if (low > high) {
return nullptr;
}
int maxIdx = 0;
int maxValue = INT_MIN;
for (int i = low; i <= high; ++i) {
if (nums[i] > maxValue) {
maxIdx = i;
maxValue = nums[i];
}
}
TreeNode* root = new TreeNode(maxValue);
root->left = build(nums, low, maxIdx-1);
root->right = build(nums, maxIdx+1, high);
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if (nums.empty()) {
return nullptr;
}
return build(nums, 0, nums.size()-1);
}
};
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.先拿一个例子看,
1
/ \
2 3
/ \ / \
5 4 8 9
/ \
6 7
preorder
1,[2,5,4,6,7],[3,8,9]
inorder
[5,2,6,4,7],1,[8,3,9]
根节点把 inorder 可以划分成两半, 然后继续递归建立树, 每次建立树在先序数组里面维护起点和终点, 在中序里面也要维护起点和终点; 所以思路是先找根节点 => 左右子树递归建树, 建树的过程需要算各种长度, 我们先写个代码框架:
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preLow, int preHigh, int inLow, int inHigh) {
if (preLow > preHigh) {
return nullptr;
}
// 找到先序的第一个就是根节点
int rootVal = preorder[preLow];
int rootInorderIdx;
for (int i = inLow; i <= inHigh; ++i) {
if (inorder[i] == rootVal) {
rootInorderIdx = i;
break;
}
}
TreeNode* root = newTreeNode(rootVal);
root->left = build(preorder, inorder, ?, ?, ?, ?);
root->right = build(preorder, inorder, ?, ?, ?, ?);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, inorder, 0, preorder.size()-1, inorder.size()-1)
}
现在需要明确上面递归构建子树的时候index怎么填, 如果能填对相应的4个index, 那么就完成了; 我们发现在中序序列里面是比较好填的, 无非就是左侧给到左子树, 右侧给到右子树
TreeNode* root = newTreeNode(rootval);
root->left = build(preorder, inorder, ?, ?, inlow, rootInorderIdx-1)
root->right = build(preorder, inorder, ?, ?, rootInorderIdx+1, inHigh)
那么先序的左边起止点怎么填?
先序左边的起点是 preLow+1, 先序的终点呢? 其实是要找到先序左侧对应的 size 有多大, 然后 preLow + leftSize;
先序右边的终点是 preHigh, 先序的起点呢? 顺着上面的结论, 其实就是左侧那个区间的后一个节点, 可以得到 preLow + leftSize + 1
leftSize = rootInorderIdx - inLow
把这些起止点都梳理清楚后, 然后就能递归的建树了
int leftSize = rootInorderIdx - inLow;
root->left = build(preorder, inorder, preLow+1, preLow+leftSize, inlow, rootInorderIdx-1);
root->right = build(preorder, inorder, preLow+leftSize+1, preHigh, rootInorderIdx+1, inHigh);
完整代码如下
class Solution {
private:
unordered_map<int, int> inorderValue2indx;
public:
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int prel, int preh, int inl, int inh) {
if (prel > preh) {
return nullptr;
}
// 找到根节点
int rootVal = preorder[prel];
int rootInorderIdx = inorderValue2indx[rootVal];
TreeNode* root = new TreeNode(rootVal);
int leftSize = rootInorderIdx - inl;
root->left = build(preorder, inorder, prel + 1, prel + leftSize, inl, rootInorderIdx - 1);
root->right = build(preorder, inorder, prel + leftSize + 1, preh, rootInorderIdx + 1, inh);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); ++i) {
inorderValue2indx[inorder[i]] = i;
}
return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size()-1);
}
};
这里有个优化点, 因为数组中不存在重复元素, 那么可以提前把中序遍历的根节点对应的index 提前保存在 hash 表中, 找 index 的时间复杂度降低为 O(1)
class Solution {
private:
// 记录下来中序遍历中每个值对应的index
unordered_map<int, int> inorderValue2indx;
public:
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int prel, int preh, int inl, int inh) {
if (prel > preh) {
return nullptr;
}
// 找到根节点
int rootVal = preorder[prel];
int rootInorderIdx = inorderValue2indx[rootVal];
TreeNode* root = new TreeNode(rootVal);
int leftSize = rootInorderIdx - inl;
root->left = build(preorder, inorder, prel + 1, prel + leftSize, inl, rootInorderIdx - 1);
root->right = build(preorder, inorder, prel + leftSize + 1, preh, rootInorderIdx + 1, inh);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); ++i) {
inorderValue2indx[inorder[i]] = i;
}
return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size()-1);
}
};
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.和前面的方法同理, 先拿一个例子看
1
/ \
2 3
/ \ / \
5 4 8 9
/ \
6 7
postorder
[5,6,7,4,2],[8,9,3],1
inorder
[5,2,6,4,7],1,[8,3,9]
根节点把 inorder 可以划分成两半, 然后继续递归建立树, 每次建立树在后序数组里面维护起点和终点, 在中序里面也要维护起点和终点
所以思路是先找根节点=>左右子树递归建树, 要写对每个 index 是怎么正确递归的, 每次拿着上面的例子去想 index 怎么构建
TreeNode* build(vector<int>& inorder, vector<int>& postorder, int inLow, int inHigh, int postLow, int postHigh) {
if (postLow > postHigh) {
return nullptr;
}
// 找到根节点
int rootVal = postorder[postHigh];
int rootInorderIdx = inorderIdx[rootVal];
TreeNode* root = newTreeNode(rootVal);
int leftSize = rootInorderIdx - inLow;
root->left = build(inorder, postorder, inLow, rootInorderIdx-1, postLow, postLow+leftSize-1);
root->right = build(inorder, postorder, rootInorderIdx+1, postHigh, postLow+leftSize, postHigh-1);
return root;
}
完整解法如下
class Solution {
private:
unordered_map<int, int> inorderRootIdx;
public:
TreeNode* build(vector<int>& inorder, vector<int>& postorder, int inLow, int inHigh, int postLow, int postHigh) {
if (postLow > postHigh) {
return nullptr;
}
int rootVal = postorder[postHigh];
int rootInorderIdx = inorderRootIdx[rootVal];
TreeNode* root = new TreeNode(rootVal);
int leftSize = rootInorderIdx - inLow;
root->left = build(inorder, postorder, inLow, rootInorderIdx-1, postLow, postLow+leftSize-1) ;
root->right = build(inorder, postorder, rootInorderIdx+1, inHigh, postLow+leftSize, postHigh-1) ;
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty()) {
return nullptr;
}
for (int i = 0; i < inorder.size(); ++i) {
inorderRootIdx[inorder[i]] = i;
}
return build(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
}
};
889.根据前序和后序遍历构造二叉树
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。示例 1: 输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
示例 2: 输入: preorder = [1], postorder = [1] 输出: [1]
分析:
1.[前序和后序构建二叉树]和 [前序中序构造二叉树]/[后序中序构造二叉树]有个本质区别, [前序和后序构建二叉树]这种构建无法确定唯一的二叉树, 而是有多种可能的结果
2.造成这种多重结果的原因是什么呢? 通过前序和和后序能找到更节点, 然后再看中序, 能唯一确定左右子树, 那么这棵树就能递归的完全定下来
3.我们没有中序的时候, 其实每次拿到根节点, 但是[左右子树确定不了]
4.举个前序和后序构造二叉树的多重结果的例子
preorder=[1,2,3]
postorder=[3,2,1]
5.递归的做法如下, 仍然是先找根节点, 然后构造左右子树的做法; 这里用一种比较自然的一类构造方法: 拿前序的根节点之后的第一个节点作为左子树的根节点
preorder
[root][[left的root][][]][[right的root][][]]
postorder
[[][][left的root]][[][][right的root]][root]
我们再去关注左子树的根节点, 在后序里面是什么位置
class Solution {
private:
unordered_map<int, int> postIdx;
public:
TreeNode* build(vector<int>& preorder, vector<int>& postorder, int preLow, int preHigh, int postLow, int postHigh) {
if (preLow > preHigh) {
return nullptr;
}
int rootVal = preorder[preLow];
// 这里有个区别, preorder区间长度为1的时候, 需要直接返回根节点, 因为再也没有preLow+1的后续左子树根节点了
if (preLow == preHigh) {
return new TreeNode(rootVal);
}
int leftRootVal = preorder[preLow+1];
int rootPostIdx = postIdx[leftRootVal];
TreeNode* root = new TreeNode(rootVal);
int leftSize = rootPostIdx - postLow + 1;
root->left = build(preorder, postorder, preLow+1, preLow+leftSize, postLow, rootPostIdx);
root->right = build(preorder, postorder, preLow+leftSize+1, preHigh, rootPostIdx+1, postHigh-1);
return root;
}
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
if (preorder.empty() || postorder.empty()) {
return nullptr;
}
for (int i = 0; i < postorder.size(); ++i) {
postIdx[postorder[i]] = i;
}
return build(preorder, postorder, 0, preorder.size()-1, 0, postorder.size()-1);
}
};
这里我们默认设置这个节点必须是左孩子节点, 实际上构造的时候也能构造成空指针的形式
int leftRootVal = preorder[preLow+1];
转载请注明来源, from goldandrabbit.github.io
