235. The nearest common ancestor of the binary search tree [LCA template + same search path]

analysis

find root To p and q The path of （ adopt while And size ）
Then see where the two paths can reach the same depth
Just return to the same deepest position

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':
        #  find root To target Of path
        def get_path(start, target):
            now = start
            path = []
            while now != target:
                path.append(now)
                #  Next level search 
                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

summary

lca Templates