algorithm - 如何找到连接二叉树中两个叶子的最长路径？

Question

如何找到通过二叉树的根连接两片叶子的最长路径的长度？

• 该函数必须是递归的，并且必须返回最长路径的长度。
• 我只需要伪代码

我刚刚读到我要找的东西叫做树的直径

标签： algorithmbinary-treegraph-algorithm

Answer 1

请注意，二叉树的直径不一定等于通过根的最长路径的长度。考虑一个完整的二叉树，它通过在根上添加一个额外的节点来修改 - 那么最佳路径根本不会通过根。

如果一定要经过根，那么最长的路径就是到达左右子树中最深节点的路径。所以考虑编写一个辅助函数来查找子树中最深的节点，看看是否可以以此为起点。