LeetCode: Smallest Subtree with all the Deepest Nodes

問題を解く

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;
    }
}