865. 具有所有最深节点的最小子树
问题描述
给定一个二叉树的根节点root，返回包含所有最深节点的最小子树的根节点。
最深节点：距离根节点最远的叶子节点
最小子树：满足条件的子树中节点数最少的那个（如果多个子树包含所有最深节点，返回深度最大的那个）
注意：
- 一个节点也可以是自己的子树
- 最深节点可能有多个
示例：
输入:root=[3,5,1,6,2,0,8,null,null,7,4]输出:[2,7,4]解释:最深节点是7和4，包含它们的最小子树根节点是23 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4输入:root=[1]输出:[1]输入:root=[0,1,3,null,2]输出:[2]解释:最深节点只有2，所以最小子树就是[2]0 / \ 1 3 \ 2算法思路
深度优先搜索 + 返回深度和节点：
核心：
- 最深节点一定在树的最大深度层
- 包含所有最深节点的最小子树 =最深节点的最近公共祖先（LCA）
关键：
- 如果左右子树的最大深度相等，说明最深节点分布在两侧，当前节点就是答案
- 如果左子树深度 > 右子树深度，答案在左子树中
- 如果右子树深度 > 左子树深度，答案在右子树中
DFS：
- 对每个节点，递归计算左右子树的最大深度
- 同时返回该子树中包含所有最深节点的最小子树根节点
- 通过比较左右子树深度来决定当前节点是否为答案
返回值：
- 方法返回一个对象，包含子树根节点和最大深度
- 或者使用全局变量记录，方法只返回深度
代码实现
方法一：返回深度和节点
classSolution{/** * 返回包含所有最深节点的最小子树 * 使用DFS返回每个子树的深度和对应的最小子树根节点 * * @param root 二叉树根节点 * @return 最小子树的根节点 */publicTreeNodesubtreeWithAllDeepest(TreeNoderoot){Resultresult=dfs(root);returnresult.node;}/** * DFS * @return Result对象，包含子树根节点和最大深度 */privateResultdfs(TreeNodenode){// 空节点：深度为0，节点为nullif(node==null){returnnewResult(null,0);}// 递归处理左右子树Resultleft=dfs(node.left);Resultright=dfs(node.right);// 如果左子树深度更大，答案在左子树中if(left.depth>right.depth){returnnewResult(left.node,left.depth+1);}// 如果右子树深度更大，答案在右子树中elseif(right.depth>left.depth){returnnewResult(right.node,right.depth+1);}// 左右子树深度相等，当前节点就是答案else{returnnewResult(node,left.depth+1);}}/** * 存储子树根节点和深度 */privatestaticclassResult{TreeNodenode;intdepth;Result(TreeNodenode,intdepth){this.node=node;this.depth=depth;}}}方法二：全局变量 + 返回深度
classSolution{privateTreeNoderesult;privateintmaxDepth;/** * 使用全局变量记录 */publicTreeNodesubtreeWithAllDeepest(TreeNoderoot){result=null;maxDepth=-1;dfs(root,0);returnresult;}/** * 返回以node为根的子树的最大深度 * 同时更新全局答案 */privateintdfs(TreeNodenode,intdepth){if(node==null){returndepth;}// 获取左右子树的最大深度intleftDepth=dfs(node.left,depth+1);intrightDepth=dfs(node.right,depth+1);// 当前子树的最大深度intcurrentMaxDepth=Math.max(leftDepth,rightDepth);// 如果左右子树深度相等，说明当前节点包含所有最深节点if(leftDepth==rightDepth){// 更新全局（深度更大的优先）if(currentMaxDepth>=maxDepth){maxDepth=currentMaxDepth;result=node;}}returncurrentMaxDepth;}}方法三：先找最深节点，再找LCA
importjava.util.*;classSolution{/** * 先找到所有最深节点，再找它们的LCA */publicTreeNodesubtreeWithAllDeepest(TreeNoderoot){if(root==null)returnnull;// 找到最大深度intmaxDepth=getMaxDepth(root);// 找到所有最深节点Set<TreeNode>deepestNodes=newHashSet<>();findDeepestNodes(root,deepestNodes,maxDepth,1);// 如果只有一个最深节点，直接返回if(deepestNodes.size()==1){returndeepestNodes.iterator().next();}// 找所有最深节点的LCAreturnfindLCA(root,deepestNodes);}privateintgetMaxDepth(TreeNodenode){if(node==null)return0;return1+Math.max(getMaxDepth(node.left),getMaxDepth(node.right));}privatevoidfindDeepestNodes(TreeNodenode,Set<TreeNode>deepestNodes,intmaxDepth,intcurrentDepth){if(node==null)return;if(currentDepth==maxDepth){deepestNodes.add(node);return;}findDeepestNodes(node.left,deepestNodes,maxDepth,currentDepth+1);findDeepestNodes(node.right,deepestNodes,maxDepth,currentDepth+1);}privateTreeNodefindLCA(TreeNodenode,Set<TreeNode>targets){if(node==null)returnnull;// 如果当前节点是最深节点之一if(targets.contains(node)){returnnode;}TreeNodeleft=findLCA(node.left,targets);TreeNoderight=findLCA(node.right,targets);// 如果左右子树都包含目标节点，当前节点是LCAif(left!=null&&right!=null){returnnode;}// 否则返回非空的一侧returnleft!=null?left:right;}}算法分析
- 时间复杂度：O(n)
- 每个节点只被访问一次
- 方法一和二只需要一次DFS遍历
- 方法三需要多次遍历总体仍是O(n)
- 空间复杂度：O(h)
- h是树的高度（递归栈空间）
- 方法一：O(h)（递归栈 + Result对象）
- 方法二：O(h)（递归栈 + 全局变量）
- 方法三：O(n)（存储最深节点的Set）
算法过程
1：root = [3,5,1,6,2,0,8,null,null,7,4]
DFS：
叶子节点（6,7,4,0,8）：
- 返回
(node, depth=1)
- 返回
节点2：
- left =
(7,1), right =(4,1) - 深度相等 → 返回
(2, 2)
- left =
节点5：
- left =
(6,1), right =(2,2) - right.depth > left.depth → 返回
(2, 3)
- left =
节点1：
- left =
(0,1), right =(8,1) - 深度相等 → 返回
(1, 2)
- left =
根节点3：
- left =
(2,3), right =(1,2) - left.depth > right.depth → 返回
(2, 4)
- left =
结果：节点2
2：root = [0,1,3,null,2]
DFS：
- 节点2：返回
(2,1) - 节点1：left =
(null,0), right =(2,1)→ 返回(2,2) - 节点3：返回
(3,1) - 根节点0：left =
(2,2), right =(3,1)→ 返回(2,3)
结果：节点2
测试用例
// TreeNode定义classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例TreeNoderoot1=newTreeNode(3);root1.left=newTreeNode(5);root1.right=newTreeNode(1);root1.left.left=newTreeNode(6);root1.left.right=newTreeNode(2);root1.right.left=newTreeNode(0);root1.right.right=newTreeNode(8);root1.left.right.left=newTreeNode(7);root1.left.right.right=newTreeNode(4);TreeNoderesult1=solution.subtreeWithAllDeepest(root1);System.out.println("Test 1: "+result1.val);// 2// 测试用例2：单节点TreeNoderoot2=newTreeNode(1);TreeNoderesult2=solution.subtreeWithAllDeepest(root2);System.out.println("Test 2: "+result2.val);// 1// 测试用例3：链状树TreeNoderoot3=newTreeNode(0);root3.left=newTreeNode(1);root3.left.right=newTreeNode(2);root3.right=newTreeNode(3);TreeNoderesult3=solution.subtreeWithAllDeepest(root3);System.out.println("Test 3: "+result3.val);// 2// 测试用例4：完全平衡树TreeNoderoot4=newTreeNode(1);root4.left=newTreeNode(2);root4.right=newTreeNode(3);TreeNoderesult4=solution.subtreeWithAllDeepest(root4);System.out.println("Test 4: "+result4.val);// 1// 测试用例5：左偏树TreeNoderoot5=newTreeNode(1);root5.left=newTreeNode(2);root5.left.left=newTreeNode(3);TreeNoderesult5=solution.subtreeWithAllDeepest(root5);System.out.println("Test 5: "+result5.val);// 3// 测试用例6：右偏树TreeNoderoot6=newTreeNode(1);root6.right=newTreeNode(2);root6.right.right=newTreeNode(3);TreeNoderesult6=solution.subtreeWithAllDeepest(root6);System.out.println("Test 6: "+result6.val);// 3// 测试用例7：三个最深节点TreeNoderoot7=newTreeNode(1);root7.left=newTreeNode(2);root7.right=newTreeNode(3);root7.left.left=newTreeNode(4);root7.left.right=newTreeNode(5);root7.right.left=newTreeNode(6);TreeNoderesult7=solution.subtreeWithAllDeepest(root7);System.out.println("Test 7: "+result7.val);// 1}}关键点
深度相等：
- 左右子树深度相等说明最深节点分布在两侧
- 当前节点是这些最深节点的最近公共祖先
为什么深度更大的优先？
要求"最小子树"，在多个满足条件的子树中，深度更大的子树包含的节点更少。递归：
- 通过比较子树深度，找到了包含所有最深节点的最小子树
- 不需要显式找到所有最深节点
边界处理：
- 空树：返回null
- 单节点：返回自身
- 只有一个最深节点：返回该节点
常见问题
为什么不用先找到所有最深节点再找LCA？
需要额外的存储空间和多次遍历。DFS一次遍历更高效。时间复杂度为什么是O(n)？
每个节点只被访问一次。
