문제를 꼼꼼히 안 읽었더니 처음에 문제 이해하는데 좀 걸렸다.
이진 트리가 주어지고, leaf node를 전부 포함하는 subtree 중 가장 작은 subtree를 구하는 것이 문제이다.
현재 node를 기준으로 왼쪽과 오른쪽 subtree의 최대 높이를 구했다.
왼쪽과 오른쪽 subtree의 높이가 동일할때 현재 node가 subtree의 시작점이 된다.
(그림을 그려보면 이해하기 쉽다.)
import java.util.*;
class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
if(root == null || (root.left == null && root.right == null)) {
return root;
}
TreeNode cur = root;
int leftDepth = getDepth(cur.left);
int rightDepth = getDepth(cur.right);
while(leftDepth != rightDepth) {
if(leftDepth > rightDepth) {
cur = cur.left;
}
if(leftDepth < rightDepth) {
cur = cur.right;
}
leftDepth = getDepth(cur.left);
rightDepth = getDepth(cur.right);
}
return cur;
}
public int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<Node> q = new LinkedList<>();
q.offer(new Node(root, 1));
int length = 1;
while(!q.isEmpty()) {
Node temp = q.poll();
if(temp.cur.left == null && temp.cur.right == null) {
if(length < temp.length) {
length = temp.length;
}
continue;
}
if(temp.cur.left != null) {
q.offer(new Node(temp.cur.left, temp.length + 1));
}
if(temp.cur.right != null) {
q.offer(new Node(temp.cur.right, temp.length + 1));
}
}
return length;
}
}
class Node {
TreeNode cur;
int length;
Node(TreeNode cur, int length) {
this.cur = cur;
this.length = length;
}
}
(내가 푼 코드를 재귀와 map을 사용해 리팩토링 할 수 있을거 같은데 나중에 해봐야지..)