---

[!info] related notes 算法面试题型 MOC 二叉树高频题

链表-二叉树-回溯

链表

带着问题去做下面的题目

• 在什么情况下，要用到哨兵节点（dummy node）？
• 在什么情况下，循环条件要写 while (node != null)？什么情况下要写 while (node.next != null)？
• 遍历链表
• 删除节点
• 插入节点
• 反转链表
• 前后指针
• 快慢指针
• 双指针
• 合并链表
• 分治
• 综合应用
• 其他

二叉树

带着问题去做下面的题目：

• 一般来说，DFS 的递归边界是空节点。在什么情况下，要额外把叶子节点作为递归边界？
• 在什么情况下，DFS 需要有返回值？什么情况下不需要有返回值？
• 在什么情况下，题目更适合用自顶向下的方法解决？什么情况下更适合用自底向上的方法解决
  • 自顶向下用于需要传递信息（深度、作为左节点或右节点的长度），即维护值

遍历二叉树

自顶向下 DFS（先序遍历）

在「递」的过程中维护值。

自底向上 DFS（后序遍历）

在「归」的过程中计算。

回溯

最近公共祖先

二叉搜索树

一般是中序遍历。

一般树

回溯

参考

分享丨【算法题单】链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树） - 讨论 - 力扣（LeetCode）