查找二叉树中给定节点最近的叶节点。二叉树中距给定节点最近的叶节点
如果树是：
1
2 3
4 5
6 7
9 8
比最短的叶节点从2是3有人可以帮我正在设计这个的算法中。谢谢。
我能够找到节点是否是根节点（通过简单的DFS），但无法为这种情况设备算法，其中节点不是最短距离叶节点的祖先。
树表示：
Class TreeNode{
int val;
TreeNode left, right;
}
，你被赋与一个节点即t1和根即t。
为了找到未加权图形中最近的节点，您需要执行BFS。给定节点的相邻节点都是其子节点及其前驱（如果有的话）。您将不得不选择树的适当表示，以便您可以找到给定节点的前任以及其子节点。
另外请注意，对于这个问题，你将不得不考虑图为无向。
您可以请多解释一下。如果我们可以有一些伪代码或代码，会很好。谢谢。 – Trying
@ user2221126遍布互联网的BFS存在伪代码 - 它是最流行的算法之一。图表中还有大量的材料。在这种情况下，你最好使用邻接表。我**可以为此问题编写一个代码，但您自己想出解决方案会更好。我相信我已经为如何做到这一点提供了足够的指导。 –
@IvayloStrandjev你不能改变树，你只需要遍历树。所以你怎么能做到这一点呢。这是面试官提到的。谢谢。 – JasonBlacket
1）找到最接近树的根叶（DFS）
2）查找给定节点的深度，如果你不知道它已经（DFS）
3）找到最接近其后代中给定节点的叶子（DFS）
该解决方案是1 + 2和3中最短的。它可能可以组合在一个DFS中。
正如@Eyal所指出的，这是错误的。
这里是修复：
1）对于树中的每个节点，找到它的后代（DFS）中最接近叶。 2）对于沿着从树根到给定节点的路径上的每个节点，添加从该节点到其最接近的后代的距离以及到给定节点的距离。
解决方案是由最小的和。从DFS算法找到了树中的所有节点的最近后代叶
开始：
您可以实现此如下。
修改递归函数，使其知道a）当前节点的深度，令Dc，b）给定节点的深度，令Dg和c）自给定节点出现以来达到的最小深度，让Ds最初设置为-1，d）迄今为止最近的节点（不一定是后代）。
在离开函数之前，如果当前节点是给定节点，则设置Dg = Ds = Dc;否则，如果Dc < Ds，则更新Ds = Dc并且保持最近的到目前为止最近的节点与当前节点的最接近的后代之间的距离Dc-Dg。
不准确。考虑树{1,1.1,1.2,1.1.1,1.1.2}，并假设1.1.1下面有一个深满的树。在这种情况下，1.1.1中最接近的叶子是1.1.2，而不是1.1.1。*或1.2。 –
非常正确，您需要尝试从树根到给定节点的路径上的所有节点的子树。感谢您指出这一点。 –
我想做一个投票，但我不能由于我的名誉:( – JasonBlacket
你尝试过什么吗？ – Balduz
请阅读我提到过的问题，以及我面临的问题。谢谢。 – JasonBlacket
发布你试过的代码 – Balduz