1123. 最深叶节点的最近公共祖先 - Kotlin DFS 深度优先搜索 递归+分类讨论

Problem: 1123. 最深叶节点的最近公共祖先

思路

由于我们无法从子节点向上找回父节点，因此在这道题中明显判断节点的高度要比判断节点的深度更加方便，我们应当用一个数据结构将所有节点的高度存储下来。

基于DFS递归获取每个节点的高度：对于任意一个根节点，其高度等于左子树的高度和右子树的高度的较大值+1，对于叶子节点，其高度为1，因此当传入的节点为null时，应当返回0。用一个哈希表将每个节点的高度存储下来以便后续操作查询。

接下来从根节点开始进行递归：

• 当当前节点的左子树高度和右子树高度相同时，说明当前节点即为所有最深节点的公共节点，返回当前节点即可
• 当当前节点的左子树高度大于右子树高度时，说明最深叶节点均在左子树上，则递归到当前节点的左节点上
• 当当前节点的左子树高度小于右子树高度时，说明最深叶节点均在右子树上，则递归到当前节点的右节点上
• 当当前节点的左节点为null时，说明最深叶节点均在右子树上，则递归到当前节点的右节点上
• 当当前节点的右节点为null时，说明最深叶节点均在左子树上，则递归到当前节点的左节点上
• 当当前节点的左右节点均为null时，说明当前节点本身即为最深节点，返回当前节点——这只会出现在整棵树只有一个最深节点的情况下
• 当当前节点为null时，说明当前传入的节点即为null，返回null——这只会出现在传入null样例的情况下

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution
fun Solution.lcaDeepestLeaves(root: TreeNode?, map: HashMap<TreeNode, Int>? = null): TreeNode? {
    if (map == null) {
        val heightMap = HashMap<TreeNode, Int>()
        freshDepth(heightMap, root)
        return lcaDeepestLeaves(root, heightMap)
    } else return when {
        (root == null) ->
            null
        (root.left == null && root.right == null) ->
            root
        (root.left == null) ->
            lcaDeepestLeaves(root.right, map)
        (root.right == null) ->
            lcaDeepestLeaves(root.left, map)
        (map[root.left]!! == map[root.right]!!) ->
            root
        (map[root.left]!! > map[root.right]!!) ->
            lcaDeepestLeaves(root.left, map)
        (map[root.left]!! < map[root.right]!!) ->
            lcaDeepestLeaves(root.right, map)
        else ->
            null
    }
}

fun Solution.freshDepth(map: HashMap<TreeNode, Int>, root: TreeNode?): Int {
    if (root == null) {
        return 0
    }
    val height = Math.max(freshDepth(map, root.left), freshDepth(map, root.right)) + 1
    map[root] = height
    return height
}