leetcode#235 Lowest Common Ancestor of a Binary Search Tree

1. 문제

2. 나의 풀이

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def find_lca(self, node , p, q):
        if node is None:
            return (0, None)
        
        left = self.find_lca(node.left, p, q)
        if left[1] is not None:
            return left

        right = self.find_lca(node.right, p, q)
        if right[1] is not None:
            return right
        
        node_count = 1 if(node == p or node == q) else 0        
        count = sum([node_count, left[0], right[0]])
        if count == 2:
            return (count, node)
        else:
            return (count, None)
        
    
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.find_lca(root, p, q)[1]

3. 남의 풀이

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def find_node(self, node , children):
        # Return Type ( member_cnt, lca)
        if node is None:
            return (0, None)
                 
        left_find = self.find_node(node.left, children)
        if(left_find[1] is not None):
            return left_find
        
        right_find = self.find_node(node.right, children)
        if(right_find[1] is not None):
            return right_find
        
        c =  left_find[0] + right_find[0] + (1 if node in children else 0)
        if c == 2:
            return (c, node)
        else:
            return (c, None)
    
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.find_node( root, [p, q])[1]

Reference