算法模式：深度优先搜索
💡
原文中文，约2100字，阅读约需5分钟。
📝
内容提要
深度优先搜索（DFS）是一种图和树的遍历算法，从未访问的顶点开始，沿路径深入，回退后探索其他路径。DFS适用于树的遍历，使用递归或栈记录父节点。文章还介绍了如何在二叉树中计算最大路径和，通过DFS获取左右子树的最大值并比较，最终返回最大路径和。
🎯
关键要点
-
深度优先搜索（DFS）是一种图和树的遍历算法，从未访问的顶点开始，沿路径深入。
-
DFS适用于树的遍历，可以使用递归或栈记录父节点。
-
在树的DFS中，可以选择前序、中序或后序遍历方式。
-
二叉树中的路径被定义为一条节点序列，路径和是路径中各节点值的总和。
-
最大路径和的计算需要比较当前节点及其左右子树的值。
-
代码示例展示了如何通过DFS计算二叉树的最大路径和。
-
思考题提到在搜索时，广度优先搜索和深度优先搜索的选择取决于工程实现的需求。
❓
延伸问答
深度优先搜索（DFS）是什么？
深度优先搜索是一种图和树的遍历算法，从未访问的顶点开始，沿路径深入，直到所有顶点都遍历完成。
如何在二叉树中计算最大路径和？
通过DFS遍历每个节点，获取左右子树的最大值，并比较当前节点及其左右子树的值，最终返回最大路径和。
深度优先搜索可以使用哪些遍历方式？
深度优先搜索可以使用前序、中序或后序遍历方式。
深度优先搜索和广度优先搜索的选择依据是什么？
选择深度优先搜索或广度优先搜索取决于具体的工程实现需求。
在深度优先搜索中如何记录父节点？
可以使用递归或显式栈来记录遍历过程中访问过的父节点。
深度优先搜索的特点是什么？
深度优先搜索的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
➡️
