298 Binary Tree Longest Consecutive Sequence
298. Binary Tree Longest Consecutive Sequence
题目： https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
难度 : Medium
思路：
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)
其实第二次递归，也就是dfs其实是有点多余的？因为可以边走边保存最大值？
因为可以
- 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
这里值得注意的是这里的self.result其实相当于dfs的全局变量，也是利用了这个才做到边递归边记录边重置。
