動機

我忘了localty

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output: 3Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output: 5Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

Sol

原本是用bfs，放node與到root的path，之後做intersection

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        pchain, qchain = None, None
        qu = deque([[root,[root]]]) # root, path to root
        while not pchain or not qchain:
            r, path = qu.popleft()
            pchain = path if not pchain and p is r else pchain
            qchain = path if not qchain and q is r else qchain
            for x in [x for x in [r.left,r.right] if x]:
                qu.append([x,path[::]+[x]])
        if len(pchain) != len(qchain):
            a,b = min([pchain,qchain], key=lambda x: len(x)), max([pchain,qchain], key=lambda x: len(x))
            while len(b) > len(a):
                if b[-1] is a[-1]:
                    return b[-1]
                else:
                    b.pop()
        else:
            a,b = pchain,qchain
        while a[-1] is not b[-1]:
            a.pop()
            b.pop()
        return a[-1]

但是如果用dfs可以一次檢查兩個ptr，但是要用global去存第一個祖先

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        
        lca = None
        
        def dfs(r):
            nonlocal lca
            
            if not r:
                return False, False
            else:
                isp,isq = (r is p), (r is q)
                if not isp or not isq:
                    a,b = dfs(r.left)
                    x,y = dfs(r.right)
                    isp, isq = (isp or a or x), (isq or b or y)
                
                if not lca and isp and isq:
                    lca = r
                return isp,isq
        
        dfs(root)
        return lca

這題保證p,q一定在tree中，這樣就只要dfs到p,q，之後只要回程檢查有沒有一個root是同時看到p,q的就是LCA 沒有看到就會是null

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q)
            return root;
        else {
            auto l = lowestCommonAncestor(root->left, p, q), r = lowestCommonAncestor(root->right, p, q);
            if (l && r) // 這裡就是LCA
                return root;
            else if (l) // 一定在其中一邊
                return l;
            else
                return r;
        }
    }
};