Elegant python solution- editing the node structure


Definition for a binary tree node

class TreeNode:
def init(self, x):
self.val = x
self.left = None
self.right = None
self.val1_ca = False #marks that this node is a common ancestor of val1
self.val2_ca = False

class Solution:
# @param A : root node of tree
# @param B : integer
# @param C : integer
# @return an integer
def lca(self, A, B, C):

    # update ca field
    A.val1_ca = A.val == B
    A.val2_ca = A.val == C
    # update right side and check ca
    if A.right is not None:
        right_ans = self.lca(A.right, B, C)
        if right_ans > -1:
            return right_ans
        A.val1_ca = A.val1_ca or A.right.val1_ca
        A.val2_ca = A.val2_ca or A.right.val2_ca
    if A.left is not None:
        left_ans = self.lca(A.left, B, C)
        if left_ans > -1:
            return left_ans
        A.val1_ca = A.val1_ca or A.left.val1_ca
        A.val2_ca = A.val2_ca or A.left.val2_ca
    if A.val1_ca and A.val2_ca:
        return A.val
    return -1