面试题库 › C++ / 后端 › C 语言由中序和后序遍历构造二叉搜索树

C 语言由中序和后序遍历构造二叉搜索树

难度 ★★☆在 0 场真实面经中被问到 方向:C++ / 后端考点:树与二叉树

答案要点

  1. 后序最后一个元素是根,中序中根左侧为左子树、右侧为右子树
  2. postIdx 从后往前取根,顺序为根→右→左,须先建右子树
  3. C 中用 malloc 建节点,postIdx 用指针传递以在递归间共享
  4. 预先建立值到中序下标的映射可达 O(n),线性查找最坏 O(n²)
  5. 前提是值互不重复;用完要后序遍历 free 释放整棵树

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题