---
# System prepended metadata

title: code tpl
tags: [mock interview, 面試]

---

# 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
=======

```python=
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)


```python=
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` `面試`