我正在使用Udacity進行在線介紹算法課程。平衡二叉樹中兩個節點之間的最短路徑如何受到路徑「權重」的影響?
在最後的評估存在的問題如下:
在安德魯·戈德堡的採訪中描述的最短路徑甲骨文, 每個節點都有一個標籤,這是在其他一些節點的列表 網絡及其到這些節點的距離。這些列表具有 屬性是:
(1)對於任何一對網絡中的節點(X,Y)的,他們的列表將在 至少一個節點Z共同
(2)最短從x到y的路徑將通過z。給定一個平衡二叉樹圖G ,對圖進行預處理,爲每個節點創建這樣的 標籤。請注意,對於大小爲n的圖形,每個標籤 中列表的大小不應大於log n。
The full question can be found here.
給定一個平衡二叉樹的約束和提示,大小不應超過數N時,直觀看來,對於一個特定節點的標籤將包括其所有的父母(如果不是葉子,也可以選擇本身)。
然而,在這個問題一些額外的教練筆記補充說:
寫您的解決方案,加權圖形工作。請注意,測試 給出,所有的邊緣有一個權重 - 這並不是特別有趣。
所以我的問題是:
如何二叉樹兩個節點之間的最短路徑由路徑是否具有重量或不會受到影響?
當然,在二叉樹中,兩個節點之間的最短路徑是唯一的簡單路徑,並且不受任何權重的影響? (除非權重可以是負數,並且路徑不必簡單,在這種情況下沒有最短路徑)
我的基本解決方案與問題中提供的簡單測試一起工作,但未能通過自動不給予反饋的平地機。
我顯然誤解的東西,但什麼......