题目地址：

https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

给定一棵二叉树，求这样的最小子树，使得该子树含全树所有最深的节点。

其实就是求所有最深节点的最近公共祖先。思路是DFS。在DFS的过程中更新全局最深节点的深度，并且先递归求解左右子树的最深节点的深度，这样就得到了全局最深节点的深度。接着看一下左右子树的最深深度是否都等于全局最深深度，如果是，则意味着左右子树都有最深节点，则说明当前节点可能是解（也有可能回溯到上面层的时候解会得到更新），则将当前节点覆盖全局答案。回溯到树根的时候全局答案就是最终答案了。代码如下：

public class Solution {private TreeNode res;private int maxDepth;public TreeNode subtreeWithAllDeepest(TreeNode root) {dfs(root, 0);return res;}private int dfs(TreeNode root, int depth) {if (root == null) {// null的深度是不能算的，要返回上一层的深度return depth - 1;}maxDepth = Math.max(maxDepth, depth);int left = dfs(root.left, depth + 1), right = dfs(root.right, depth + 1);if (left == right && left == maxDepth) {res = root;}return Math.max(left, right);}
}class TreeNode {int val;TreeNode left, right;public TreeNode(int val) {this.val = val;}
}

时间复杂度$O(n)$，空间$O(h)$。