title: 构造二叉树 ， 看这一篇就足够！
思想：构造整棵树 = 根节点 + 构造左子树 + 构造右子树
📃 题目一描述
题目链接：从中序与后序遍历构造二叉树
🔔 解题思路
必须明确条件： 给出一个数组的值中，是没有重复的数字的，即没用节点的数值是相同的！
画图分析：（图来自dong哥）
可以很明确得知：后续遍历数组中postEnd就是中点的值，通过中点的值我们就可以在中序遍历数组中找到中点的位置，从而分割出左子树，右子树，递归就可以完成构建；
class Solution {
public:
TreeNode* buildTree(vector& inorder, vector& postorder) {
return build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
//都是不同的值组成，不存在"中"在左子树中出现的情况；
TreeNode* build(vector& inorder, int inStart, int inEnd, vector& postorder, int postStart, int postEnd) {
if (inStart > inEnd) return nullptr;
int rootVal = postorder[postEnd];
int size = 0;
for (int i = inStart; i left = build(inorder, inStart, inStart + size - 1, postorder, postStart, postStart + size - 1);
root->right = build(inorder, inStart + size + 1, inEnd, postorder, postStart + size, postEnd - 1);
return root;
}
};
📃 题目二描述
题目链接：从前序与中序遍历构造二叉树
🔔 解题思路
同上，依据图来写代码即可：
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* build(vector& preorder, int preStart, int preEnd, vector& inorder, int inStart, int inEnd) {
if (preStart > preEnd) return nullptr;
int rootVal = preorder[preStart];
int size = 0;
for (int i = inStart; i left = build(preorder, preStart + 1, preStart + size, inorder, inStart, inStart + size - 1);
root->right = build(preorder, preStart + size + 1, preEnd, inorder, inStart + size + 1, inEnd);
return root;
}
};
📃 题目三描述
题目链接：根据前序和后序遍历构造二叉树
🔔 解题思路
这道题与前两道题的不同之处： 通过前序和后序是无法确定唯一一颗二叉树的！
原因：看图
前序和后序只能确定中，无法确定左右的边界！可能压根就没有左指针或者右指针 例如： preorder = [1,2,3], postorder = [3,2,1]，而下图两种树结构都满足；
理解： 我们假设前序遍历的第二个元素是左子树的根节点（左图），但实际上左子树有可能是空指针（右图），那么这个元素就应该是右子树的根节点。由于这里无法确切进行判断，所以导致了最终答案的不唯一。
这道题如何做： ①确定根节点，②将前序遍历数组中根节点后的下一位为左根节点（preStart + 1， 自己也快选定其他）， ③在后序遍历数组中找到该左根节点的位置，从而分割左右子树；如图：
代码：
class Solution {
public:
TreeNode* constructFromPrePost(vector& preorder, vector& postorder) {
return build(preorder, 0, preorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode* build(vector& preorder, int preStart, int preEnd, vector& postorder, int postStart, int postEnd) {
if (preStart > preEnd) return nullptr;
int rootVal = preorder[preStart];
if (preStart == preEnd) return new TreeNode(rootVal);
int leftRootVal = preorder[preStart + 1];
int size = 0;
for (int i = postStart; i left = build(preorder, preStart + 1, preStart + size + 1, postorder, postStart, postStart + size);
root->right = build(preorder, preStart + size + 2, preEnd, postorder, postStart + size + 1, postEnd);
return root;
}
};
优化建议：以上三题，均是不重复数组，可以用空间换时间的想法： 可以采用哈希表记录 需要遍历的数组 对应的index， 这样在每次遍历的时候可以直接得到想要查询数的下标；
📃 题目四描述（简单练手题）
题目链接：最大二叉树
🔔 解题思路
根据构造树的思想，依题目构造即可
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector& nums) {
return build(nums, 0, nums.size() - 1);
}
TreeNode* build(vector& nums, int start, int end) {
if (start > end) return nullptr;
int rootVal = INT_MIN;
int index = 0;
for (int i = start; i left = build(nums, start, index - 1);
root->right = build(nums, index + 1, end);
return root;
}
};
Original: https://www.cnblogs.com/D-booker/p/16319675.html
Author: D-booker
Title: 14. 构造二叉树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/713319/
转载文章受原作者版权保护。转载请注明原作者出处！