class Solution:
# @param A : root node of tree
# @return an integer
def solveUtil(self,A):
if A == None:
return (0,0)
leftMax,leftIncludingMax = self.solveUtil(A.left)
rightMax,rightIncludingMax = self.solveUtil(A.right)
currentIncludingMax = 1
if A.left != None and A.left.val == A.val + 1:
currentIncludingMax = max(currentIncludingMax,leftIncludingMax+1)
if A.right != None and A.right.val == A.val + 1:
currentIncludingMax = max(currentIncludingMax,rightIncludingMax+1)
return (max(leftMax,rightMax,currentIncludingMax),currentIncludingMax)
def solve(self, A):
return self.solveUtil(A)[0]
Python O(N) solution Not getting accepted (TLE)
ankit_maurya
#1