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

发表于 分类于 阅读次数：

方法1

思路

获取每个节点的父节点
记录p所有的祖先节点
q节点不断向祖先移动，若有祖先在p的祖先节点中，则该祖先为p、q的最近公共祖先

时间复杂度

O(n)

空间复杂度

O(n)

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.node_to_father = dict()

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.node_to_father = dict()
        self.traverse_tree(root)

        visited_node_set = set()
        while p:
            visited_node_set.add(p.val)
            p = self.node_to_father.get(p.val)

        while q:
            if q.val in visited_node_set:
                return q
            q = self.node_to_father.get(q.val)
        
    def traverse_tree(self, root):
        if root.left:
            self.node_to_father[root.left.val] = root
            self.traverse_tree(root.left)
        
        if root.right:
            self.node_to_father[root.right.val] = root
            self.traverse_tree(root.right)

方法2

思路

两种情况：
1、p不是q的祖先节点（反之亦然）
从root结点开始遍历节点，若存在节点，p（或q）在其左子树找到 且 q（或p）在其右子树找到，则该节点就是p、q的最近公共祖先
2、p是q的祖先节点（反之亦然）
从root结点开始遍历节点，若存在节点等于p（或q），则该节点就是p、q的最近公共祖先

时间复杂度

O(n)

空间复杂度

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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 

        if p.val == root.val or q.val == root.val:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left and right:
            return root
        if left:
            return left
        if right:
            return right