Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-07-12 00:37:02
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/
863. All Nodes Distance K in Binary Tree
給你一個二元樹的根節點 root,另一個在 root 的節點 target 表示目標節點,以及一
個數字 k ,找出所有距離 target 節點為 k 的節點編號。
(題目的所有節點編號都是獨特的)
Example 1:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/28/sketch0.png
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value
5) have values 7, 4, and 1.
Example 2:
Input: root = [1], target = 1, k = 3
Output: []
思路:
1.找距離某個節點為X的所有節點可以用BFS去找,在做之前要先做兩個處理。
2.先找出 target 節點,因為我們要以他為中心進行BFS。
3.把二元樹轉成無向圖,因為二元樹不支持往上遍歷,這樣才可以找target上面的節點
距離。
4.用一個Set來避免無向圖死循環。
5.當BFS的深度為 k 的時候就把節點編號加入結果集。
Java Code:

Links booklink

Contact Us: admin [ a t ] ucptt.com