# 298 Binary Tree Longest Consecutive Sequence

### 298. Binary Tree Longest Consecutive Sequence

TLE代码，每个node求，然后求最大值

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

class Solution(object):
def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def consecutive(root):
if root == None:
return 0
else:
left, right = 0,0
if root.left:
if root.left.val == root.val + 1:
left = 1 + consecutive(root.left)
if root.right:
if root.right.val == root.val + 1:
right = 1 + consecutive(root.right)
return max(left, right, 1)

def dfs(root):
s = []
s.append(root)
while s:
root = s.pop()
res.append(consecutive(root))
if root.left:
s.append(root.left)
if root.right:
s.append(root.right)
if not root:
return 0

res = []
dfs(root)
return max(res)



• recursion,在参数中包含当前的连续seq长度
• 如果left, right child的value是连续的，那么就将长度+1传入下一个call

AC代码

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

class Solution(object):
def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(root, curLen):
self.result = max(curLen, self.result)
if root.left:
if root.left.val == root.val + 1:
dfs(root.left, curLen + 1)
else:
dfs(root.left, 1)
if root.right:
if root.right.val == root.val + 1:
dfs(root.right, curLen + 1)
else:
dfs(root.right,1)

if not root: return 0

self.result = 0
dfs(root, 1)
return self.result



apachecn/AiLearning