给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。
回想一下：
叶节点 是二叉树中没有子节点的节点
树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。
示例 2：
输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。
示例 3：
输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。
提示：
树中的节点数将在 [1, 1000] 的范围内。
0 <= Node.val <= 1000
每个节点的值都是 独一无二 的。
思路：
此题和865. 具有所有最深节点的最小子树一样；
子问题：
如果左子树深度比右子树深，那么最深的叶子结点肯定在左边，最近公共祖先也肯定在左子树那边；
如果右子树深度比左子树深，那么最深的叶子结点肯定在右边，最近公共祖先也肯定在右子树那边；
如果左右两边深度一样，那么最下面那一层肯定都是叶子节点，所以最近公共祖先就是当前结点；
定义一个深度搜索函数depth，去求结点的深度；
在lcaDeepestLeaves函数里面判断，如果是左边深还是右边深还是一样深；
class Solution {
public:
//求当前结点的深度
int depth(TreeNode* root){
if(!root) return 0;
int left = depth(root->left);
int right = depth(root->right);
return 1+max(left, right);
}
TreeNode* lcaDeepestLeaves(TreeNode* root) {
if(!root) return NULL;
int left = depth(root->left); //左树深度
int right = depth(root->right); //右树深度
if(left == right){ //如果左右两边深度相等，那么当前结点就是最近公共祖先
return root;
}
else if(left>right){ //左边更深，那么就去左边找
return lcaDeepestLeaves(root->left);
}
else{
return lcaDeepestLeaves(root->right);
}
}
};
解题思路
题解中有很多利用左子树和右子树高度信息来求解，但对于我没接触到这种思路的时候，我自己其实是很难想到在短时间内想到这种解答的。在这里介绍一种很容易就想到的思路。
利用层序遍历，得到最深的叶子节点。若最深的叶子节点只有一个的话，那这个最深的叶子节点的最近公共祖先就是它自己。
最深的叶子节点不止一个的话，求最深叶子节点们的最近公共祖先。
from collections import deque
class Solution:
def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
# 得到最深的叶子结点
lastLevelNode = self.getDeeppestNodes(root)
# 如果最深叶子结点只有一个的话，那它的最近祖先就是它自己
if len(lastLevelNode) == 1:
return lastLevelNode[0]
# 否则获取叶子结点们的最近公共祖先
return self.getLca(root, lastLevelNode)
# 使用层序遍历获得最深的叶子结点
def getDeeppestNodes(self, root):
queue = deque([root])
while queue:
level = []
for i in range(len(queue)):
node = queue.popleft()
level.append(node)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
lastLevelNode = level
return lastLevelNode
# 求最深的叶子结点的最近公共祖先
def getLca(self, node, lastLevelNode):
if not node:
return None
# 如果当前节点是最深的叶子结点，该节点的最近公共祖先就是自己
if node in lastLevelNode:
return node
# 否则到左孩子去找叶子结点的最近公共祖先
left = self.getLca(node.left, lastLevelNode)
# 到右孩子去找叶子结点的最近公共祖先
right = self.getLca(node.right, lastLevelNode)
# 在左孩子和右孩子中都找到了，叶子结点们的最近公共祖先只能是node自己
if left != None and right != None:
return node
# 左边没找到，那最近公共祖先肯定就在右边
if left == None:
return right
# 右边没找到，那最近公共祖先肯定就在左边
if right == None:
return left
