面试题库 › C++ / 后端 › 恢复二叉搜索树中被交换的两个节点

恢复二叉搜索树中被交换的两个节点

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

哪些公司问过

腾讯1多益网络1

常见岗位:Web 前端、游戏服务端

答案要点

  1. 二叉搜索树中序遍历递增,被交换后出现逆序对
  2. 相邻交换只有一处逆序;不相邻有两处逆序
  3. 第一个错误节点是第一处逆序的前一个,第二个是最后一处逆序的后一个
  4. 中序遍历记录 prev,发现逆序时更新 first 和 second,最后交换值
  5. 时间 O(n),空间 O(h);要求 O(1) 空间用 Morris 遍历

易错点

面试官常见追问

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

相关面试题