数据结构——树（02构造二叉树，代码练习）

一、构造二叉树1

序号	题目	链接
1	先序+中序	https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=problem-list-v2&envId=tree
2	后序+中序	https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=problem-list-v2&envId=tree
3	先序+后序	https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/?envType=problem-list-v2&envId=tree

1.1先序+中序 构造二叉树

给定二叉树的前序遍历（根→左→右）和中序遍历（左→根→右）序列，重建二叉树。

• Step1：先序找到根节点【前序遍历的第一个元素是根节点】
• Step2：中序找到根节点
• Step3：左侧为左子树，右侧为右子树
• Step4：递归处理左、右子树（根据左右子树长度截取前序和中序的对应子序列）。

例子：先序（ABDECFGH）、中序（DBEACGFH）

• 根节点（A）。中序遍历中找到A的位置：【DBE】 A 【CGFH】
• 左子树：节点数量为 3（leftsize），先序遍历中【根节点 A 之后的 3 个元素】是左子树的先序遍历：BDE。
  因此左子树的中序遍历为（DBE），左子树的先序遍历为（BDE）
• 右子树：节点数量为 4 （n-leftsize-1），先序遍历中【剩余的元素】是右子树的先序遍历：CFGH。
  因此右子树的中序遍历为（CGFH），右子树的先序遍历为（CFGH）
  

按照上述的思路，重复多次就能构造出整个树了

private:// 存储中序遍历值到索引的映射，用于快速查找unordered_map<int, int> inorderMap;// 递归辅助函数TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {// 递归终止条件：子树为空if (preStart > preEnd) return nullptr;// 1、先序找到根节点：先序遍历的第一个元素是当前子树的根节点int rootVal = preorder[preStart];TreeNode* root = new TreeNode(rootVal);// 2、中序找到根节点（借助map）int rootIndex = inorderMap[rootVal];// 3、计算左子树的节点数量（右子树的数量也已知了）int leftSize = rootIndex - inStart;// 4、递归构造左子树root->left = build(preorder, preStart + 1, preStart + leftSize,inorder, inStart, rootIndex - 1);// 5、递归构造右子树root->right = build(preorder, preStart + leftSize + 1, preEnd,inorder, rootIndex + 1, inEnd);return root;}public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n=preorder.size();// 构建中序遍历值到索引的映射for (int i = 0; i < n; ++i) {inorderMap[inorder[i]] = i;}// 调用递归辅助函数return build(preorder, 0, n- 1,inorder, 0, n- 1);}

1.2后序+中序 构造二叉树

给定中序（左→根→右）和后序（左→右→根）遍历序列，重建二叉树。

• Step1：后序找到根节点【后序遍历的最后一个元素是根节点】
• Step2：中序找到根节点
• Step3：左侧为左子树，右侧为右子树
• Step4：递归处理左、右子树（根据左右子树长度截取前序和中序的对应子序列）。

例子：后序（DEBGHFCA）、中序（DBEACGFH）

• 根节点（A）。中序遍历中找到A的位置：【DBE】 A 【CGFH】
• 左子树：节点数量为 3（leftsize），后序遍历中【前3个元素】是左子树的后序遍历：DEB。
  因此左子树的中序遍历为（DBE），左子树的后序遍历为（DEB）
• 右子树：节点数量为 4 （n-leftsize-1），先序遍历中【根节点之前的4个元素】是右子树的后序遍历：GHFC。
  因此右子树的中序遍历为（CGFH），右子树的先序遍历为（GHFC）
  

按照上述的思路，重复多次就能构造出整个树了。

private:// 存储中序遍历值到索引的映射，用于快速查找unordered_map<int, int> inorderMap;// 递归辅助函数TreeNode* build(vector<int>& postorder, int postStart, int postEnd, vector<int>& inorder, int inStart, int inEnd) {// 递归终止条件：子树为空if (postStart > postEnd)  return nullptr;       // 1、后序找到根节点，后序遍历的最后一个元素是当前子树的根节点int rootVal = postorder[postEnd];TreeNode* root = new TreeNode(rootVal); // 2、找到根节点在中序遍历中的位置（借助map）int rootIndex = inorderMap[rootVal];// 3、计算左子树的节点数量int leftSize = rootIndex - inStart;// 4、递归构造左子树root->left = build(postorder, postStart, postStart + leftSize - 1,inorder, inStart, rootIndex - 1);// 5、递归构造右子树root->right = build(postorder, postStart + leftSize, postEnd - 1,inorder, rootIndex + 1, inEnd);return root;}public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n=postorder.size();// 构建中序遍历值到索引的映射for (int i = 0; i < inorder.size(); ++i) {inorderMap[inorder[i]] = i;}// 调用递归辅助函数return build(postorder, 0, n-1,inorder, 0, n-1);}

1.3先序+后序 构造二叉树

先序+后序 并不能唯一确定一颗二叉树。

• Step1：先序找到根节点【先序遍历的第一个元素是根节点】
• Step2：先序找到左子树的根节点【先序遍历的第二个元素是左子树的根节点】
• Step3：后序遍历中找到左子树根节点的位置，确定左子树的大小
• Step4：递归构建左子树和右子树。

unordered_map<int,int> M;
TreeNode* f(vector<int>& pre,int preS,int preE,vector<int>& post,int postS,int postE){if(preS>preE) return nullptr;int rootVal=pre[preS];TreeNode* root=new TreeNode(rootVal);//只剩一个节点if(preS==preE) return root;//先序遍历找到左子树的根节点——后序遍历索引——左子树节点数int leftRootVal=pre[preS+1];int leftRootIndex=M[leftRootVal];int leftsize=leftRootIndex-postS+1;//递归构建左右子树root->left=f(pre,preS+1,preS+leftsize,post,postS,leftRootIndex);root->right=f(pre,preS+leftsize+1,preE,post,leftRootIndex+1,postE-1);return root;
}
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {int n=preorder.size();for(int i=0;i<n;i++){M[postorder[i]]=i;}return f(preorder,0,n-1,postorder,0,n-1);
}

1.4层序+中序 构造二叉树

暂无。

二、构造二叉树2

序号	题目	链接
1	二叉树展开为链表	https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/?envType=problem-list-v2&envId=tree
2	合并二叉树	https://leetcode.cn/problems/merge-two-binary-trees/description/?envType=problem-list-v2&envId=tree
3	翻转二叉树	https://leetcode.cn/problems/invert-binary-tree/description/?envType=problem-list-v2&envId=tree