二叉树的相关知识

二叉树的相关知识

问题一：知道二叉树的后序遍历和中序遍历，如何得到前序遍历

我的想法：

1. 遍历后序序列，找到根结点

2. 在前序序列中找到你刚刚找到的根结点

3. 根据找到的根结点，把前序列表中的序列分为两部分，一部分为根结点的左子树，另一部分为根结点的右子树

4. 分别遍历左子树和右子树

5. 再重复之前的前3步

6. 直到一个序列没有左子树与右子树后，把这个子结点加到根结点的左或右子树

困扰我的点：

1. 用什么数据结构来存储二叉树

   • 数组：适合完全二叉树、树大小已知的场景，实现简单、访问快；
   • 指针：适合任意二叉树、树大小不确定的场景，空间灵活、逻辑直观。

   最常用的是链式结构（通过指针 / 引用关联节点），每个节点包含：

   • 自身值（val）
   • 左子树指针（left）
   • 右子树指针（right）

   struct node{int val;node* left;node* right;
   }struct TreeNode {int val;         // 节点值TreeNode* left;  // 左子树指针TreeNode* right; // 右子树指针TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} //这是构造函数
   };
   

2. 遍历后序序列，找到根结点后，如何拆分左、右子树

   • 两个序列的左子树对应的下标范围是一致的(这是错的，只有在两个序列开始下标为0开始时是正确的)

     根据后序和中序遍历序列构建二叉树

     TreeNode* buildTree(vector<int>& post, int postStart, int postEnd, vector<int>& in, int inStart, int inEnd, unordered_map<int, int>& inMap)

     参数列表：（后序序列，后序序列的起点，后续序列的终点，中序序列，中序序列的终点，中序序列值与下标的对应map（可有可无，可用循环实现））；

     一共6个参数

     拆分左、右子树就是如何构建这6个参数！

     左子树：

     // 可不可以直接使用root

     // index 为root在中序序列中的下标，所以可以在中序序列的范围中使用

     root -> left = bulidTree(post, poststart, poststart + leftSize - 1, in, inStart, index - 1, inMap)

     右子树：

     root -> right = bulidTree(post, postStart + leftSize, postEnd - 1, in, index + 1, inEnd, inMap)

   优化

   优化前：

   TreeNode* buildTree(vector<int>& post, int postStart, int postEnd, vector<int>& in, int inStart, int inEnd, unordered_map<int, int>& inMap)

   优化后：

   TreeNode* buildTree(int subroot, int inStart, int inEnd)

   在构造二叉树时，后续序列的起点与终点的作用主要是用来得到根节点，我们可以直接将参数列表加一个root的下标即可

3. 之后左右子树的根结点怎么确定

   子树的根节点是其对应后序序列的最后一个元素

4. 如何判断这个递归该结束直接返回

   当子树的节点数量为 0时，递归终止，返回nullptr。
   具体表现为：后序序列的起始索引 > 结束索引（或中序序列的起始索引 > 结束索引）。
   例如：

   • 左子树的左子树：中序序列为空（inStart > inEnd），此时返回nullptr
   • 右子树的右子树：如果节点已处理完（postStart > postEnd），返回nullptr

   if (postStart > postEnd || inStart > inEnd) {return nullptr; // 子树无节点，递归终止
   }
   

5. 什么时候把这个子结点加到根结点的左或右子树

   在递归构建完子树后，将子树的根节点赋值给当前根的左 / 右指针。
   步骤：

   1. 先创建当前根节点
   2. 递归构建左子树，赋值给root->left
   3. 递归构建右子树，赋值给root->right

总结：核心逻辑链

1. 从后序末尾取根节点 → 2. 在中序中找根位置，拆分左 / 右子树的中序序列 → 3. 根据左子树节点数，拆分左 / 右子树的后序序列 → 4. 递归构建左 / 右子树，挂到当前根的左右指针 → 5. 当子树无节点时（索引越界），递归终止。

扩展点

1. TreeNode* root = new TreeNode(rootVal); 是 动态内存分配结合带参数构造函数

2. 链式结构的实现

   指针是 “地址工具”，动态数组是 “连续内存块”；指针可以指向动态数组的首地址，帮助我们操作动态数组，但指针本身不是动态数组。

   比如：你用 “钥匙（指针）” 打开 “房间（动态数组）”，钥匙和房间是两个东西 —— 钥匙是工具，房间是存储物品的空间。

   所以可以通过指针来实现链式结构

3. 二叉树的 索引规律（按层次序列）

   • 若父节点索引为 i，则左子节点索引为 2i + 1，右子节点索引为 2i + 2；
   • 若子节点索引为 j，则父节点索引为 (j - 1) // 2（整数除法）。

4. 为什么不用数组来实现二叉树的存储

   • 空间浪费严重:若不是完全二叉树，会浪费大量空间
   • 插入 / 删除不灵活：若要在非叶子节点插入子节点，可能需要移动后续大量元素（破坏原有下标规律）
   • 逻辑不直观：无法直接通过节点本身找到子节点（需依赖下标计算），尤其不适合递归构建（如你 PAT 题中 “后序 + 中序转树” 的场景）。

   递归插入结点的算法适合使用链式结构

5. 顺序结构与链式结构的比较

   • 数组(顺序结构)：适合完全二叉树、树大小已知的场景，实现简单、访问快；结点 <= 30;

     也可以用map来实现；

   • 指针(链式结构)：适合任意二叉树、树大小不确定的场景，空间灵活、逻辑直观。

   最常用的是链式结构（通过指针 / 引用关联节点）

   代码实现：(链式结构)

   #include <iostream>
   #include <vector>
   #include <unordered_map>
   #include <queue>
   using namespace std;vector<int> post(35), in(35);
   unordered_map<int, int> inMap;
   // 二叉树节点定义
   struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   };// 根据后序和中序遍历序列构建二叉树
   TreeNode* buildTree(int subroot, int inStart, int inEnd) {// 递归终止条件：区间无效if (inStart > inEnd) {return nullptr;}	// 后序遍历的最后一个元素是当前根节点int rootVal = post[subroot];TreeNode* root = new TreeNode(rootVal);// 找到根节点在中序遍历中的位置int inRoot = inMap[rootVal];root->left = buildTree(subroot - (inEnd - inRoot + 1), inStart, inRoot - 1);root->right = buildTree(subroot - 1, inRoot + 1, inEnd);return root;
   }// 层序遍历二叉树
   vector<int> levelOrder(TreeNode* root) {vector<int> res;if (!root) return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();res.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}return res;
   }int main() {int N;cin >> N;// 读取后序遍历序列for (int i = 0; i < N; ++i) {cin >> post[i];}// 读取中序遍历序列并建立值到下标的映射for (int i = 0; i < N; ++i) {cin >> in[i];inMap[in[i]] = i;}// 构建二叉树TreeNode* root = buildTree(N-1, 0, N-1);vector<int> result = levelOrder(root);for (int i = 0; i < result.size(); ++i) {if (i > 0) cout << " ";cout << result[i];}cout << endl;return 0;
   }