具有所有最深节点的最小子树Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给定一个根为 root 的二叉树，每个节点的深度是该节点到根的最短距离。

返回包含原始树中所有最深节点的最小子树。

如果一个节点在整个树的任意节点之间具有最大的深度，则该节点是最深的。

一个节点的子树是该节点加上它的所有后代的集合。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。

提示：

树中节点的数量在 [1, 500] 范围内。
0 <= Node.val <= 500
每个节点的值都是独一无二的。

# 思路

递归

# 解法


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {

           if(root==null)
    	   return null;
       else {
    	   int ldep=maxDepth(root.left),rdep=maxDepth(root.right);
    	   if(ldep==rdep)
    		   return root;
    	   else if(ldep>rdep)
    		   return subtreeWithAllDeepest(root.left);
    	   else
    		   return subtreeWithAllDeepest(root.right);
       }
    }
    
    
    int maxDepth(TreeNode root) {
    	if(root==null)
    		return 0;
    	else
    		return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 总结

分析出几种情况，然后分别对各个情况实现