给定一个根为 root
的二叉树,每个节点的深度是 该节点到根的最短距离 。
如果一个节点在 整个树 的任意节点之间具有最大的深度,则该节点是 最深的 。
一个节点的 子树 是该节点加上它的所有后代的集合。
返回能满足 以该节点为根的子树中包含所有最深的节点 这一条件的具有最大深度的节点。
注意:本题与力扣 1123 重复:https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/
示例 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.
# 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 not root:
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]
/**
* 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)[0];
}
private TreeNode[] dfs(TreeNode root) {
if (root == null) {
return new TreeNode[]{null, new TreeNode(0)};
}
TreeNode[] left = dfs(root.left);
TreeNode[] right = dfs(root.right);
int d1 = left[1].val, d2 = right[1].val;
if (d1 > d2) {
return new TreeNode[]{left[0], new TreeNode(d1 + 1)};
}
if (d1 < d2) {
return new TreeNode[]{right[0], new TreeNode(d2 + 1)};
}
return new TreeNode[]{root, new TreeNode(d1 + 1)};
}
}
/**
* 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) {}
* };
*/
class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
return dfs(root).first;
}
pair<TreeNode*, int> dfs(TreeNode* root) {
if (!root) return {nullptr, 0};
auto left = dfs(root->left);
auto right = dfs(root->right);
int d1 = left.second, d2 = right.second;
if (d1 > d2) return {left.first, d1 + 1};
if (d1 < d2) return {right.first, d2 + 1};
return {root, d1 + 1};
}
};
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type Result struct {
Node *TreeNode
Depth int
}
func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
return dfs(root).Node
}
func dfs(root *TreeNode) Result {
if root == nil {
return Result{
nil, 0,
}
}
left, right := dfs(root.Left), dfs(root.Right)
d1, d2 := left.Depth, right.Depth
if d1 > d2 {
return Result{left.Node, d1 + 1}
}
if d1 < d2 {
return Result{right.Node, d2 + 1}
}
return Result{root, d1 + 1}
}