# 0865. Smallest Subtree with all the Deepest Nodes
###### tags: `Leetcode` `Medium` `FaceBook` `BFS` `Lowest Common Ancestor`
Link: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

## 思路
BFS 找到最后一层的第一个node和最后一个node
然后找第一个node和最后一个的lowest common ancestor
## Code

class Solution {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        TreeNode first = null;
        TreeNode last = null;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                TreeNode curr = q.poll();
                if(i == 0){
                    first = curr;
                }
                if(i == size-1){
                    last = curr;
                }
                if(curr.left!=null) q.add(curr.left);
                if(curr.right!=null) q.add(curr.right);
            }
        }
        return lca(root, first, last);
    }
    public TreeNode lca(TreeNode root, TreeNode p, TreeNode q){
        if(root==null || root==p || root==q) return root;
        TreeNode left = lca(root.left, p, q);
        TreeNode right = lca(root.right, p, q);
        if(left!=null&right!=null) return root;
        if(left!=null) return left;
        return right;
    }
}