C 语言由中序和后序遍历构造二叉搜索树
答案要点
- 后序最后一个元素是根,中序中根左侧为左子树、右侧为右子树
- postIdx 从后往前取根,顺序为根→右→左,须先建右子树
- C 中用 malloc 建节点,postIdx 用指针传递以在递归间共享
- 预先建立值到中序下标的映射可达 O(n),线性查找最坏 O(n²)
- 前提是值互不重复;用完要后序遍历 free 释放整棵树
易错点
- 先建左子树再建右子树,导致后序下标错位
- postIdx 按值传递,递归返回后下标不更新
- 没处理重复值,中序定位根会出错
- malloc 后不检查返回值、不释放内存
面试官常见追问
- 如果是前序和中序怎么做?
- 只给前序和后序能唯一确定二叉树吗?
- 如果只给后序且是二叉搜索树呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场