題目連結:
題目意譯:
給定一棵二元樹的根節點 root、目標節點的數值 target 以及一個整數 k。回傳一個陣列其由所有與目標節點距離 k 的節點之數值所組成。
你可以按任意順序排列答案。
限制:
樹中的節點數位於範圍 [1, 500] 中。
0 ≦ Node.val ≦ 500
所有 Node.val 之值彼此相異。
target 為樹中的其中一個節點之值。
0 ≦ k ≦ 1000
範例測資:
範例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
輸出: [7,4,1]
解釋: 那些距離目標節點(其值為 5)為 2 的節點之數值為 7 、 4 和 1。
範例 2:
輸入: root = [1], target = 1, k = 3
輸出: []
解題思維:
先用一次深度優先搜尋(Depth First Search,DFS)或是廣度優先搜尋(Breadth First Search,BFS)找到目標節點在樹中的何處,然後順便把每一個節點的父母節點紀錄起來以便「回頭」。
然後接著再從目標節點所在地用 BFS 擴張到 k 步遠即可找到所有所求的數值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。