LeetCode: Smallest Subtree with all the Deepest Nodes

문제를 꼼꼼히 안 읽었더니 처음에 문제 이해하는데 좀 걸렸다.
이진 트리가 주어지고, 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을 사용해 리팩토링 할 수 있을거 같은데 나중에 해봐야지..)