二叉樹中距給定節點最近的葉節點

Question

查找二叉樹中給定節點最近的葉節點。

如果樹是：

     1 

       2   3 

      4  5 

     6  7 

    9  8 

比最短的葉節點從2是3有人可以幫我正在設計這個的算法中。謝謝。

我能夠找到節點是否是根節點（通過簡單的DFS），但無法爲這種情況設備算法，其中節點不是最短距離葉節點的祖先。

樹表示：

Class TreeNode{ 
    int val; 
    TreeNode left, right; 
} 

，你被賦與一個節點即t1和根即t。

Answer 1

爲了找到未加權圖形中最近的節點，您需要執行BFS。給定節點的相鄰節點都是其子節點及其前驅（如果有的話）。您將不得不選擇樹的適當表示，以便您可以找到給定節點的前任以及其子節點。

另外請注意，對於這個問題，你將不得不考慮圖爲無向。

Answer 2

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。