前往
大廳
主題

LeetCode - 0863. All Nodes Distance K in Binary Tree 解題心得

Not In My Back Yard | 2024-03-15 12:00:01 | 巴幣 0 | 人氣 44

題目連結:


題目意譯:
給定一棵二元樹的根節點 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 步遠即可找到所有所求的數值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作