原題

給一棵二叉樹和二叉樹中的兩個節(jié)點，找到這兩個節(jié)點的最近公共祖先LCA。

兩個節(jié)點的最近公共祖先，是指兩個節(jié)點的所有父親節(jié)點中（包括這兩個節(jié)點），離這兩個節(jié)點最近的公共的節(jié)點。

每個節(jié)點除了左右兒子指針以外，還包含一個父親指針parent，指向自己的父親。

對于下面的這棵二叉樹

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7

解題思路

• 根據(jù)p，一路向上找到所有的parent，得到一個list
• 根據(jù)q，一路向上找到所有的parent，得到一個list
• 從左向右看兩個list，最先一樣的node即為公共祖先

完整代碼

"""
Definition of ParentTreeNode:
class ParentTreeNode:
    def __init__(self, val):
        this.val = val
        this.parent, this.left, this.right = None, None, None
"""
class Solution:
    """
    @param root: The root of the tree
    @param A and B: Two node in the tree
    @return: The lowest common ancestor of A and B
    """ 
    def lowestCommonAncestorII(self, root, p, q):
        list = []
        while p:
            list.append(p)
            p = p.parent
        
        while q:
            if q in list:
                return q
            q = q.parent