【数据结构与算法】第21篇：二叉树遍历的经典问题：由遍历序列重构二叉树

一、为什么能唯一确定一棵二叉树1.1 需要哪些序列前序中序可以唯一确定一棵二叉树后序中序可以唯一确定一棵二叉树前序后序不能唯一确定当节点只有单子树时无法区分左右1.2 核心思想以“前序中序”为例前序遍历的第一个节点是根节点在中序遍历中根节点左边是左子树右边是右子树根据左子树的节点个数可以在前序序列中划分出左子树和右子树的范围递归处理左右子树text前序[根] [左子树前序] [右子树前序] 中序[左子树中序] [根] [右子树中序]二、前序中序重构二叉树2.1 手动推导示例已知前序[1, 2, 4, 5, 3, 6]中序[4, 2, 5, 1, 3, 6]第1步前序第一个是1 → 根节点为1第2步在中序中找到1左边[4,2,5]是左子树右边[3,6]是右子树text1 / \ 左子树 右子树第3步左子树有3个节点对应前序中根后面的3个[2,4,5]左子树递归前序[2,4,5]→ 根是2中序[4,2,5]→ 2左边是4右边是5text1 / \ 2 右子树 / \ 4 5第4步右子树有2个节点对应前序中剩余[3,6]右子树递归前序[3,6]→ 根是3中序[3,6]→ 3左边空右边是6text1 / \ 2 3 / \ \ 4 5 62.2 代码实现c#include stdio.h #include stdlib.h typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode; TreeNode* createNode(int value) { TreeNode *node (TreeNode*)malloc(sizeof(TreeNode)); node-data value; node-left NULL; node-right NULL; return node; } // 在中序序列中查找根节点的位置 int findIndex(int *inorder, int start, int end, int value) { for (int i start; i end; i) { if (inorder[i] value) { return i; } } return -1; } // 前序中序重构 // preStart, preEnd: 前序序列的起止索引 // inStart, inEnd: 中序序列的起止索引 TreeNode* buildFromPreIn(int *preorder, int preStart, int preEnd, int *inorder, int inStart, int inEnd) { if (preStart preEnd || inStart inEnd) { return NULL; } // 前序第一个是根 int rootVal preorder[preStart]; TreeNode *root createNode(rootVal); // 在中序中找到根的位置 int rootIndex findIndex(inorder, inStart, inEnd, rootVal); int leftSize rootIndex - inStart; // 左子树节点个数 // 递归构建左右子树 root-left buildFromPreIn(preorder, preStart 1, preStart leftSize, inorder, inStart, rootIndex - 1); root-right buildFromPreIn(preorder, preStart leftSize 1, preEnd, inorder, rootIndex 1, inEnd); return root; } // 辅助函数包装调用 TreeNode* buildTreePreIn(int *preorder, int *inorder, int n) { return buildFromPreIn(preorder, 0, n - 1, inorder, 0, n - 1); }三、后序中序重构二叉树3.1 手动推导示例已知后序[4, 5, 2, 6, 3, 1]中序[4, 2, 5, 1, 3, 6]第1步后序最后一个是1 → 根节点为1第2步在中序中找到1左边[4,2,5]是左子树右边[3,6]是右子树第3步左子树有3个节点对应后序中前面的3个[4,5,2]左子树递归后序[4,5,2]→ 根是2中序[4,2,5]→ 2左边是4右边是5第4步右子树有2个节点对应后序中剩余[6,3]右子树递归后序[6,3]→ 根是3中序[3,6]→ 3左边空右边是6结果与之前相同。3.2 代码实现c// 后序中序重构 // postStart, postEnd: 后序序列的起止索引 // inStart, inEnd: 中序序列的起止索引 TreeNode* buildFromPostIn(int *postorder, int postStart, int postEnd, int *inorder, int inStart, int inEnd) { if (postStart postEnd || inStart inEnd) { return NULL; } // 后序最后一个是根 int rootVal postorder[postEnd]; TreeNode *root createNode(rootVal); // 在中序中找到根的位置 int rootIndex findIndex(inorder, inStart, inEnd, rootVal); int leftSize rootIndex - inStart; // 左子树节点个数 int rightSize inEnd - rootIndex; // 右子树节点个数 // 递归构建左右子树 root-left buildFromPostIn(postorder, postStart, postStart leftSize - 1, inorder, inStart, rootIndex - 1); root-right buildFromPostIn(postorder, postEnd - rightSize, postEnd - 1, inorder, rootIndex 1, inEnd); return root; } // 辅助函数 TreeNode* buildTreePostIn(int *postorder, int *inorder, int n) { return buildFromPostIn(postorder, 0, n - 1, inorder, 0, n - 1); }四、完整代码演示c#include stdio.h #include stdlib.h typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode; TreeNode* createNode(int value) { TreeNode *node (TreeNode*)malloc(sizeof(TreeNode)); node-data value; node-left NULL; node-right NULL; return node; } int findIndex(int *arr, int start, int end, int value) { for (int i start; i end; i) { if (arr[i] value) return i; } return -1; } // 前序中序 TreeNode* buildFromPreIn(int *preorder, int preStart, int preEnd, int *inorder, int inStart, int inEnd) { if (preStart preEnd || inStart inEnd) return NULL; int rootVal preorder[preStart]; TreeNode *root createNode(rootVal); int rootIndex findIndex(inorder, inStart, inEnd, rootVal); int leftSize rootIndex - inStart; root-left buildFromPreIn(preorder, preStart 1, preStart leftSize, inorder, inStart, rootIndex - 1); root-right buildFromPreIn(preorder, preStart leftSize 1, preEnd, inorder, rootIndex 1, inEnd); return root; } // 后序中序 TreeNode* buildFromPostIn(int *postorder, int postStart, int postEnd, int *inorder, int inStart, int inEnd) { if (postStart postEnd || inStart inEnd) return NULL; int rootVal postorder[postEnd]; TreeNode *root createNode(rootVal); int rootIndex findIndex(inorder, inStart, inEnd, rootVal); int leftSize rootIndex - inStart; root-left buildFromPostIn(postorder, postStart, postStart leftSize - 1, inorder, inStart, rootIndex - 1); root-right buildFromPostIn(postorder, postStart leftSize, postEnd - 1, inorder, rootIndex 1, inEnd); return root; } // 遍历验证 void preorder(TreeNode *root) { if (root NULL) return; printf(%d , root-data); preorder(root-left); preorder(root-right); } void inorder(TreeNode *root) { if (root NULL) return; inorder(root-left); printf(%d , root-data); inorder(root-right); } void postorder(TreeNode *root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%d , root-data); } void freeTree(TreeNode *root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); } int main() { // 原始树的前序、中序、后序 int preorder_seq[] {1, 2, 4, 5, 3, 6}; int inorder_seq[] {4, 2, 5, 1, 3, 6}; int postorder_seq[] {4, 5, 2, 6, 3, 1}; int n sizeof(preorder_seq) / sizeof(preorder_seq[0]); printf( 前序中序重构 \n); printf(前序: ); for (int i 0; i n; i) printf(%d , preorder_seq[i]); printf(\n中序: ); for (int i 0; i n; i) printf(%d , inorder_seq[i]); printf(\n); TreeNode *tree1 buildTreePreIn(preorder_seq, inorder_seq, n); printf(重构后的前序遍历: ); preorder(tree1); printf(\n重构后的中序遍历: ); inorder(tree1); printf(\n); printf(\n 后序中序重构 \n); printf(后序: ); for (int i 0; i n; i) printf(%d , postorder_seq[i]); printf(\n中序: ); for (int i 0; i n; i) printf(%d , inorder_seq[i]); printf(\n); TreeNode *tree2 buildTreePostIn(postorder_seq, inorder_seq, n); printf(重构后的后序遍历: ); postorder(tree2); printf(\n重构后的中序遍历: ); inorder(tree2); printf(\n); freeTree(tree1); freeTree(tree2); return 0; }运行结果text 前序中序重构 前序: 1 2 4 5 3 6 中序: 4 2 5 1 3 6 重构后的前序遍历: 1 2 4 5 3 6 重构后的中序遍历: 4 2 5 1 3 6 后序中序重构 后序: 4 5 2 6 3 1 中序: 4 2 5 1 3 6 重构后的后序遍历: 4 5 2 6 3 1 重构后的中序遍历: 4 2 5 1 3 6五、递归分治过程图解以“前序中序”为例递归划分过程text第1层 前序 [1 | 2 4 5 | 3 6] 中序 [4 2 5 | 1 | 3 6] 左子树 根 右子树 第2层左子树 前序 [2 | 4 | 5] 中序 [4 | 2 | 5] 左 根 右 第2层右子树 前序 [3 | 6] 中序 [3 | 6] 根 右六、复杂度分析操作时间复杂度空间复杂度查找根节点O(n)每层遍历-优化版哈希表O(1)O(n)整体O(n²) 最坏 / O(n) 优化O(n)递归栈哈希表优化方法用哈希表存储中序序列中每个值的位置查找根节点变为O(1)。七、小结这一篇我们学习了由遍历序列重构二叉树已知序列可行性核心思路前序中序✓前序确定根中序分左右后序中序✓后序确定根中序分左右前序后序✗单子树时无法区分左右递归分治模板text1. 从前序或后序中取出根节点 2. 在中序中找到根的位置 3. 计算左子树节点个数 4. 递归构建左子树 5. 递归构建右子树下一篇我们讲线索二叉树。八、思考题已知前序[1,2,3]后序[3,2,1]能唯一确定一棵二叉树吗为什么如果二叉树节点值可以重复前序中序还能唯一确定吗尝试用哈希表优化查找根节点的过程将时间复杂度降到O(n)。给定层序和中序如何重构二叉树欢迎在评论区讨论你的答案。