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

题目描述

给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

回想一下：

叶节点 是二叉树中没有子节点的节点
树的根节点的深度为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

示例 1：

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

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。

提示：

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

解法一：BFS

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    var queue []*TreeNode
    parents := make(map[*TreeNode]*TreeNode)
    parents[root] = nil
    queue = append(queue, root)
    for len(queue) > 0 {
        cnt := len(queue)
        var tmp []*TreeNode
        for i := 0; i < cnt; i++ {
            cur := queue[i]
            if cur.Left != nil {
                tmp = append(tmp, cur.Left)
                parents[cur.Left] = cur
            }
            if cur.Right != nil {
                tmp = append(tmp, cur.Right)
                parents[cur.Right] = cur
            }
        }
        if len(tmp) == 0 {
            break
        } else {
            queue = tmp
        }
    }

    findGrandfather := func(left, right *TreeNode) (int, *TreeNode) {
        weight := 0
        for parents[left] != parents[right] {
            left, right = parents[left], parents[right]
            weight++
        }
        return weight, parents[left]
    }
    ansWeight, ansNode := math.MinInt32, queue[0]
    for i := 1; i < len(queue); i++ {
        weight, grandfather := findGrandfather(queue[i-1], queue[i])
        if weight > ansWeight {
            ansWeight = weight
            ansNode = grandfather
        }
    }
    return ansNode
}

解法二：DFS

 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


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    // dfs 返回如下两个结果
    // 结果二为以 root 节点为根的二叉树的最深叶节点的最近公共祖先
    // 结果一为以<结果二返回的节点>为根的二叉树的高度
    var dfs func(root *TreeNode) (int, *TreeNode)
    dfs = func(root *TreeNode) (int, *TreeNode) {
        if root == nil {
            return 0, nil
        }
        lH, lAns := dfs(root.Left)
        rH, rAns := dfs(root.Right)
        if lH == rH {
            return lH + 1, root
        } else if lH > rH {
            return lH + 1, lAns
        } else { // rH > lH
            return rH + 1, rAns
        }
    }
    _, ans := dfs(root)
    return ans
}