<div id="readability-page-1" class="page"><div><h2 id="문제">문제</h2>
<a href="https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/">Number of Good Leaf Nodes Pairs</a>
<h2 id="풀이">풀이</h2>
<ul>
<li>두 말단 노드의 거리가 distacne 이하인 쌍의 개수를 찾는 문제</li>
<li>주어진 Tree를 Graph로 구성하고, leaves를 구해놓은다</li>
<li>구한 leaves 를 순회하면서 bfs로 각 말단노드와 노드간 거리를 구한다.<ul>
<li>거리가 distance보다 크면 탐색 종료</li>
<li>거리가 distance보다 적으면서 해당 노드가 leaves에 포함되면 cnt 증가</li>
</ul></li>
</ul>
<h2 id="코드">코드</h2>
<pre><code>class Solution {
 private int distance;
 private Map&lt;TreeNode, List&lt;TreeNode&gt;&gt; graph;
 private Set&lt;TreeNode&gt; leaves;
 
 public int countPairs(TreeNode root, int distance) {

 this.distance = distance;
 this.leaves = new HashSet();
 this.graph = new HashMap();
 
 // 각 노드 간 거리를 계산하기 위해 주어진 root를 통해 graph를 양방향 인접리스트로 구성한다
 getGraph(root, null);
 
 int pairs = 0;
 for(TreeNode leaf : leaves){
 pairs += bfs(leaf);
 }
 
 return pairs / 2;
 }
 
 public void getGraph(TreeNode node, TreeNode parent){
 if(node == null) return;
 
 // left, righ 둘 다 말단 노드인 경우는 leaves에 추가
 if(node.left == null &amp;&amp; node.right == null){
 leaves.add(node);
 }
 
 // 부모 노드가 있는 경우 양방향으로 그래프 추가
 if(parent != null){
 graph.computeIfAbsent(parent, k -&gt; new ArrayList&lt;&gt;()).add(node);
 graph.computeIfAbsent(node, k -&gt; new ArrayList&lt;&gt;()).add(parent);
 }
 
 // 왼쪽, 오른쪽 트리 탐색하기 위해서 재귀 탐색
 getGraph(node.left, node);
 getGraph(node.right, node); 
 }
 
 public int bfs(TreeNode leaf){
 // queue에는 {node, dist} 로 저장
 Queue&lt;Pair&gt; queue = new LinkedList&lt;&gt;();
 Set&lt;TreeNode&gt; visited = new HashSet();
 
 queue.add(new Pair(leaf, 0));
 visited.add(leaf);
 
 int cnt = 0;
 
 while(!queue.isEmpty()){
 Pair pair = queue.poll();
 TreeNode node = pair.node;
 int dist = pair.dist;
 
 // 두 말단 노드의 거리가 distance 이상이면 탐색 안 함
 if(dist &gt; distance) continue;
 
 if(dist &gt; 0 &amp;&amp; leaves.contains(node)){
 // distance 범위 내 말단노드를 찾으면 cnt++;
 cnt++;
 }
 
 for(TreeNode nextNode : graph.getOrDefault(node, Collections.emptyList())){
 if(!visited.contains(nextNode)){
 visited.add(nextNode);
 queue.add(new Pair(nextNode, dist + 1));
 }
 }
 }
 
 return cnt;
 }
 
 class Pair {
 TreeNode node;
 int dist;

 public Pair(TreeNode node, int dist){
 this.node = node;
 this.dist = dist;
 }
 }
}
</code></pre>
<h2 id="정리">정리</h2>
<ul>
<li>TreeNode 순회하며서 level를 증가시켜 각 노드마다 level를 부여하고, level이 가장 큰 노드들을 단말 노드로 정하고 다시 순회하면서 해당 단말 노드들이 distance 안에 있나를 체크하는 식으로 하려고 했다가, 단말 노드들이 level이 다를 수 있음 + 코드가 저세상으로 가버려서 포기 </li>
<li>먼저 TreeNode를 순회하면서 leaves를 구하는 것을 생각하지 못해서 결국 코드 참조해서 풀었다. 어려웠다.</li>
<li>핵심은 leaves를 구해놓고, 모든 node를 bfs/dfs로 탐색하면서 distance 보다 작은지 &amp;&amp; contains 되었는지 찾는 문제..</li>
</ul></div></div>

삶도 재입학이 되나요?

문제
Number of Good Leaf Nodes Pairs
풀이
두 말단 노드의 거리가 distacne 이하인 쌍의 개수를 찾는 문제
주어진 Tree를 Graph로 구성하고, leaves를 구해놓은다
구한 leaves 를 순회하면서 bfs로 각 말단노드와 노드간 거리를 구한다.
거리가 distance보다 크면 탐색 종료
거리가 distance보다 적으면서 해당 노드가 leaves에 포함되면 cnt 증가
코드
class Solution {
 private int distance;
 private Map<TreeNode, List<TreeNode>> graph;
 private Set<TreeNode> leaves;
 public int countPairs(TreeNode root, int distance) {
 this.distance = distance;
 this.leaves = new HashSet();
 this.graph = new HashMap();
 // 각 노드 간 거리를 계산하기 위해 주어진 root를 통해 graph를 양방향 인접리스트로 구성한다
 getGraph(root, null);
 int pairs = 0;
 for(TreeNode leaf : leaves){
 pairs += bfs(leaf);
 }
 return pairs / 2;
 }
 public void getGraph(TreeNode node, TreeNode parent){
 if(node == null) return;
 // left, righ 둘 다 말단 노드인 경우는 leaves에 추가
 if(node.left == null && node.right == null){
 leaves.add(node);
 }
 // 부모 노드가 있는 경우 양방향으로 그래프 추가
 if(parent != null){
 graph.computeIfAbsent(parent, k -> new ArrayList<>()).add(node);
 graph.computeIfAbsent(node, k -> new ArrayList<>()).add(parent);
 }
 // 왼쪽, 오른쪽 트리 탐색하기 위해서 재귀 탐색
 getGraph(node.left, node);
 getGraph(node.right, node); 
 }
 public int bfs(TreeNode leaf){
 // queue에는 {node, dist} 로 저장
 Queue<Pair> queue = new LinkedList<>();
 Set<TreeNode> visited = new HashSet();
 queue.add(new Pair(leaf, 0));
 visited.add(leaf);
 int cnt = 0;
 while(!queue.isEmpty()){
 Pair pair = queue.poll();
 TreeNode node = pair.node;
 int dist = pair.dist;
 // 두 말단 노드의 거리가 distance 이상이면 탐색 안 함
 if(dist > distance) continue;
 if(dist > 0 && leaves.contains(node)){
 // distance 범위 내 말단노드를 찾으면 cnt++;
 cnt++;
 }
 for(TreeNode nextNode : graph.getOrDefault(node, Collections.emptyList())){
 if(!visited.contains(nextNode)){
 visited.add(nextNode);
 queue.add(new Pair(nextNode, dist + 1));
 }
 }
 }
 return cnt;
 }
 class Pair {
 TreeNode node;
 int dist;
 public Pair(TreeNode node, int dist){
 this.node = node;
 this.dist = dist;
 }
 }
}
정리
TreeNode 순회하며서 level를 증가시켜 각 노드마다 level를 부여하고, level이 가장 큰 노드들을 단말 노드로 정하고 다시 순회하면서 해당 단말 노드들이 distance 안에 있나를 체크하는 식으로 하려고 했다가, 단말 노드들이 level이 다를 수 있음 + 코드가 저세상으로 가버려서 포기 
먼저 TreeNode를 순회하면서 leaves를 구하는 것을 생각하지 못해서 결국 코드 참조해서 풀었다. 어려웠다.
핵심은 leaves를 구해놓고, 모든 node를 bfs/dfs로 탐색하면서 distance 보다 작은지 && contains 되었는지 찾는 문제..

99클럽 코테 스터디 32일차 - bfs

댓글