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