树
深度优先搜索
广度优先搜索
哈希表
二叉树
题目描述
给定一个根为 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
每个节点的值都是 独一无二 的。
注意: 本题与力扣 1123 重复:https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves
解法
方法一
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def subtreeWithAllDeepest ( self , root : TreeNode ) -> TreeNode :
def dfs ( root ):
if root is None :
return None , 0
l , d1 = dfs ( root . left )
r , d2 = dfs ( root . right )
if d1 > d2 :
return l , d1 + 1
if d1 < d2 :
return r , d2 + 1
return root , d1 + 1
return dfs ( root )[ 0 ]
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 /**
* 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 ) {
return dfs ( root ). getKey ();
}
private Pair < TreeNode , Integer > dfs ( TreeNode root ) {
if ( root == null ) {
return new Pair <> ( null , 0 );
}
Pair < TreeNode , Integer > l = dfs ( root . left );
Pair < TreeNode , Integer > r = dfs ( root . right );
int d1 = l . getValue (), d2 = r . getValue ();
if ( d1 > d2 ) {
return new Pair <> ( l . getKey (), d1 + 1 );
}
if ( d1 < d2 ) {
return new Pair <> ( r . getKey (), d2 + 1 );
}
return new Pair <> ( root , d1 + 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 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
using pti = pair < TreeNode * , int > ;
class Solution {
public :
TreeNode * subtreeWithAllDeepest ( TreeNode * root ) {
return dfs ( root ). first ;
}
pti dfs ( TreeNode * root ) {
if ( ! root ) return { nullptr , 0 };
pti l = dfs ( root -> left );
pti r = dfs ( root -> right );
int d1 = l . second , d2 = r . second ;
if ( d1 > d2 ) return { l . first , d1 + 1 };
if ( d1 < d2 ) return { r . first , d2 + 1 };
return { root , d1 + 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 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type pair struct {
first * TreeNode
second int
}
func subtreeWithAllDeepest ( root * TreeNode ) * TreeNode {
var dfs func ( root * TreeNode ) pair
dfs = func ( root * TreeNode ) pair {
if root == nil {
return pair { nil , 0 }
}
l , r := dfs ( root . Left ), dfs ( root . Right )
d1 , d2 := l . second , r . second
if d1 > d2 {
return pair { l . first , d1 + 1 }
}
if d1 < d2 {
return pair { r . first , d2 + 1 }
}
return pair { root , d1 + 1 }
}
return dfs ( root ). first
}
GitHub