leetcode 1650. 二叉树的最近公共祖先 III

发表于 分类于 阅读次数：

解题思路

同 leetcode 236. 二叉树的最近公共祖先 方法1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        p_parent_set = set()
        while p:
            p_parent_set.add(p.val)
            p = p.parent

        while q:
            if q.val in p_parent_set:
                return q
            q = q.parent