题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个二叉树和两个节点，现在要找到这两个节点的最近公共祖先。

思路分享

  • 灵神的思路是真的好，对于 p 和 q 这两个指定点，一旦遍历到就可以归，因为再往下找没有意义。对于其它为空的分支就返回空，如果一个节点只有左或右，就返回有的一边，如果左右都有，说明这就是最近公共祖先，就返回当前节点。

    https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solutions/2023872/fen-lei-tao-lun-luan-ru-ma-yi-ge-shi-pin-2r95/

  • 这里补充一下为什么再往下找没有意义，如果到某个地方找到其中一个点 p，剩下的点 q 有两个情况，一个是这个 q 在 p 之下，那么直接返回 p 就是最近公共祖先；如果 q 在 p 外，或者同级，那么这是其它分支会返回结果，也与 p 下面无关，所以不用再往下找。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None 
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if root is p or root is q:
            return root
        if left and right:
            return root 
        if left:
            return left 
        if right:
            return right