算法题 具有所有最深节点的最小子树

865. 具有所有最深节点的最小子树

问题描述

给定一个二叉树的根节点root，返回包含所有最深节点的最小子树的根节点。

最深节点：距离根节点最远的叶子节点
最小子树：满足条件的子树中节点数最少的那个（如果多个子树包含所有最深节点，返回深度最大的那个）

注意：

• 一个节点也可以是自己的子树
• 最深节点可能有多个

示例：

输入:root=[3,5,1,6,2,0,8,null,null,7,4]输出:[2,7,4]解释:最深节点是7和4，包含它们的最小子树根节点是2

3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4

输入:root=[1]输出:[1]

输入:root=[0,1,3,null,2]输出:[2]解释:最深节点只有2，所以最小子树就是[2]

0 / \ 1 3 \ 2

算法思路

深度优先搜索 + 返回深度和节点：

1. 核心：

   • 最深节点一定在树的最大深度层
   • 包含所有最深节点的最小子树 =最深节点的最近公共祖先（LCA）

2. 关键：

   • 如果左右子树的最大深度相等，说明最深节点分布在两侧，当前节点就是答案
   • 如果左子树深度 > 右子树深度，答案在左子树中
   • 如果右子树深度 > 左子树深度，答案在右子树中

3. DFS：

   • 对每个节点，递归计算左右子树的最大深度
   • 同时返回该子树中包含所有最深节点的最小子树根节点
   • 通过比较左右子树深度来决定当前节点是否为答案

4. 返回值：

   • 方法返回一个对象，包含子树根节点和最大深度
   • 或者使用全局变量记录，方法只返回深度

代码实现

方法一：返回深度和节点

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：

1. 叶子节点（6,7,4,0,8）：

   • 返回(node, depth=1)

2. 节点2：

   • left =(7,1), right =(4,1)
   • 深度相等 → 返回(2, 2)

3. 节点5：

   • left =(6,1), right =(2,2)
   • right.depth > left.depth → 返回(2, 3)

4. 节点1：

   • left =(0,1), right =(8,1)
   • 深度相等 → 返回(1, 2)

5. 根节点3：

   • left =(2,3), right =(1,2)
   • left.depth > right.depth → 返回(2, 4)

结果：节点2

2：root = [0,1,3,null,2]

DFS：

1. 节点2：返回(2,1)
2. 节点1：left =(null,0), right =(2,1)→ 返回(2,2)
3. 节点3：返回(3,1)
4. 根节点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}}

关键点

1. 深度相等：

   • 左右子树深度相等说明最深节点分布在两侧
   • 当前节点是这些最深节点的最近公共祖先

2. 为什么深度更大的优先？
   要求"最小子树"，在多个满足条件的子树中，深度更大的子树包含的节点更少。

3. 递归：

   • 通过比较子树深度，找到了包含所有最深节点的最小子树
   • 不需要显式找到所有最深节点

4. 边界处理：

   • 空树：返回null
   • 单节点：返回自身
   • 只有一个最深节点：返回该节点

常见问题

1. 为什么不用先找到所有最深节点再找LCA？
   需要额外的存储空间和多次遍历。DFS一次遍历更高效。

2. 时间复杂度为什么是O(n)？
   每个节点只被访问一次。