面试题库 › C++ / 后端 › 验证二叉搜索树(迭代中序遍历)

验证二叉搜索树(迭代中序遍历)

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

哪些公司问过

字节跳动1

常见岗位:后端开发

答案要点

  1. BST 中序遍历严格递增,逐个与前驱比较即可判定
  2. 迭代中序:左链压栈、弹栈访问、转向右子树,直到栈空且指针为空
  3. 前驱用指针或标志表示,不用 INT_MIN 等哨兵值,防止边界值误判
  4. 重复值按题意通常视为非法,比较时用小于等于
  5. 时间 O(n),空间 O(h);也可递归传上下界

易错点

面试官常见追问

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

相关面试题