474 · 最近公共祖先 II - LintCode

Difficulty
Medium
Tags
二叉树
URL
https://www.lintcode.com/problem/474/
Star
描述
给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。
两个节点的最近公共祖先，是指两个节点的所有父亲节点中（包括这两个节点），离这两个节点最近的公共的节点。
每个节点除了左右儿子指针以外，还包含一个父亲指针parent，指向自己的父亲。
样例
样例 1:
输入：{4,3,7,#,#,5,6},3,5
输出：4
解释：
     4
     / \
    3   7
       / \
      5   6
LCA(3, 5) = 4
样例 2:
输入：{4,3,7,#,#,5,6},5,6
输出：7
解释：
      4
     / \
    3   7
       / \
      5   6
LCA(5, 6) = 7

法 1 链表找交汇节点

思路
因为有了指向 parent的节点，所以就转化为了找链表的交汇节点
题解
"""
Definition of ParentTreeNode:
class ParentTreeNode:
    def __init__(self, val):
        self.val = val
        self.parent, self.left, self.right = None, None, None
"""


class Solution:
    """
    @param: root: The root of the tree
    @param: A: node in the tree
    @param: B: node in the tree
    @return: The lowest common ancestor of A and B
    """
    def lowestCommonAncestorII(self, root, A, B):
        # write your code here
        temp_a, temp_b = A, B
        while temp_a != temp_b:
            temp_a = temp_a.parent if temp_a else B
            temp_b = temp_b.parent if temp_b else A
        return temp_a

法 2 用hashset 来记录

思路
用hashset来记录走过的点，当当前走的点在hashset中时，说明是交汇节点
题解
"""
Definition of ParentTreeNode:
class ParentTreeNode:
    def __init__(self, val):
        self.val = val
        self.parent, self.left, self.right = None, None, None
"""


class Solution:
    """
    @param: root: The root of the tree
    @param: A: node in the tree
    @param: B: node in the tree
    @return: The lowest common ancestor of A and B
    """
    def lowestCommonAncestorII(self, root, A, B):
        # write your code here
        hash_set = set()
        while A or B:
            if A:
                if A in hash_set:
                    return A
                hash_set.add(A)
                A = A.parent
            if B:
                if B in hash_set:
                    return B
                hash_set.add(B)
                B = B.parent

        return None