題目出處
474 · Lowest Common Ancestor II
難度
easy
個人範例程式碼
"""
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):
# use hashset
path_of_A = set()
while(A):
path_of_A.add(A)
A = A.parent
while(B):
if B in path_of_A:
return B
else:
B = B.parent
return None
算法說明
LCA 的基本題型,或是說更簡單的,這題中的 TreeNode 設計中多了 parent,使題目更簡單了。
我們可以快速使用 set() 幫我們記憶路徑,從底部往上找 parent,
兩者對比後即可快速得到答案。
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解