235. 二叉搜索樹的最近公共祖先【lca模板 + 找路徑相同】

分析

找到root到p和q的路徑（通過while和大小關系即可）
然後看看兩條路徑最深能到哪裏相同
返回最深的相同的比特置即可

ac code

# 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':
        # 找到root到target的path
        def get_path(start, target):
            now = start
            path = []
            while now != target:
                path.append(now)
                # 下一層尋找
                if target.val > now.val:
                    now = now.right
                else:
                    now = now.left
            path.append(target)
            return path
        
        pa = get_path(root, p)
        pb = get_path(root, q)

        ans = None
        for u, v in zip(pa, pb):
            if u == v:
                ans = u
            else:
                break
        
        return ans

總結

lca模板