# 236. Lowest Common Ancestor of a Binary Tree

node {
left
right
}

Lonlg Common Anestor

root, p, q

two node for their
1. recursive for reach node, return potential LCA
2. if find p or q return
4. if left and right are not None -> i am LCA
5. if one (l or r) is not None -> return potential LCA

4. if one (l or r) is not None -> propagate to parent node
a. truly LCA
b. potentially one side of LCA

p->LCA LCA->root q->LCA = q->LCA LCA->root p->LCA

======
0
1 2
3 4

p = 3, q = 1
=======

def lca(root, p, q):
    
    def helper(node):
        if not node or node == p or node == q:
            return node
        
        l = helper(node.left)
        r = helper(node.right)
        if l and r:
            # LCA
            return node
        
        # one side is LCA, potential LCA
        return l or r
    
    return helper(root)

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

# two pointer from left rght
# def helper(leftm right)
# return (left +1 , right) (left , right-1)

def findPalindrome(s):
    self.idx = -1
    
    def helper(left, right, skip):
        while left < right:
            if s[left] != s[right]:
                if skip == 0:
                    return False
                a = helper(left+1, right, skip-1)
                if a:
                    self.idx = left
                    return True
                b = helper(left, right-1, skip-1)
                if b:
                    self.idx = right
                    return True
            left += 1
            right -= 1
        return True
    
    ret = helper(0, len(s)-1, 1)
    if ret:
        if self.idx == -1:
            return s
        return s[:self.idx] + s[self.idx+1:]
    return ""
    # TC O(N)

###### tags: `mock interview` `面試`