1123. 最深叶子节点的最近公共祖先

问题1123 最深叶子节点的最近公共祖先 ★★☆☆☆

https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/

题目本身并不难理解，一颗二叉树，每个节点都有一个depth，根节点depth为0，每往下每一层depth加1。这些节点中有一些是叶子节点，即没有孩子的节点。这些叶子节点可能有不同的depth，我们把depth最大的那些叶子节点挑出来。问题来了，这些被挑选出来的depth最大的叶子节点，它们的最小公共祖先是哪个节点？

我一开始的解题思路是层序遍历，并维护起来每个节点的父节点，根据层序遍历找到的depth最大的节点集合，通过维护的父节点信息去定位最小公共祖先。这种方法可以解决这个问题，不过代码看起来繁杂一些，效率也较差。

看了一下官方题解，有点意思，确实思路更显高级，代码也更简洁。关键点在于想明白这样一点：根据题目要求，最小公共祖先出现在depth较大的那颗子树上，如果左右子树的depth相等，那么当前的根节点就是最小公共祖先。

	public TreeNode lcaDeepestLeaves(TreeNode root) {
		List<Object> ret = recur(root);
		return (TreeNode) ret.get(1);
	}

	private List<Object> recur(TreeNode node) {
		if (node == null) {
			return Arrays.asList(0, null);
		}

		List<Object> left = recur(node.left);
		List<Object> right = recur(node.right);

		int leftDepth = (int) left.get(0);
		TreeNode leftLca = (TreeNode) left.get(1);
		int rightDepth = (int) right.get(0);
		TreeNode rightLca = (TreeNode) right.get(1);
		if (leftDepth > rightDepth) {
			return Arrays.asList(leftDepth + 1, leftLca);
		} else if (leftDepth < rightDepth) {
			return Arrays.asList(rightDepth + 1, rightLca);
		} else {
			return Arrays.asList(leftDepth + 1, node);
		}
	}

在 LeetCode 查看