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