0865. Smallest Subtree with all the Deepest Nodes¶
题目信息¶
- 题号:
0865
- 难度:
Medium
- 主题:
二叉树、最深节点、最小包含子树
- 原题:
- 重点:
最深节点按距根节点的最大深度确定;返回以某个原树节点为根、包含全部最深节点的最小子树根节点
题目重述¶
给定一棵二叉树。节点深度定义为从根节点到该节点最短路径上的边数;具有全树最大深度的节点称为最深节点。
请返回原树中的一个节点,使以它为根的子树包含全部最深节点,并且在满足该条件的所有子树中范围最小。若只有一个最深节点,答案就是该节点本身;若有多个,答案等价于它们在树中的最低公共祖先。
树中节点数在 [1, 500] 范围内,节点值在 [0, 500] 范围内且互不相同。
自建示例¶
最深节点位于根的不同分支:
输入:root = [1,2,3,4,null,null,5]
输出:节点 1
解释:节点 4 和 5 都位于深度 2,分别处在根的左右子树中;包含二者的最小子树只能以根节点 1 为根。
全树只有一个最深节点:
输入:root = [6,2,null,9]
输出:节点 9
解释:节点 9 是唯一位于最大深度 2 的节点。以它自身为根的子树已经包含全部最深节点,并且比任何祖先子树都小。