FilesExpand file tree

master

/

longest_consecutive.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

45 lines (40 loc) · 901 Bytes

master

/

longest_consecutive.py

Copy path

Top

File metadata and controls

• Code
• Blame

45 lines (40 loc) · 901 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

# Given a binary tree, find the length of the longest consecutive sequence path.

# The path refers to any sequence of nodes from some starting node to any node

# in the tree along the parent-child connections.

# The longest consecutive path need to be from parent to child

# (cannot be the reverse).

# For example,

# 1

# \

# 3

# / \

# 2 4

# \

# 5

# Longest consecutive sequence path is 3-4-5, so return 3.

# 2

# \

# 3

# /

# 2

# /

# 1

maxlen = 0

def longestConsecutive(root):

"""

:type root: TreeNode

:rtype: int

"""

if not root:

return 0

DFS(root, 0, root.val)

return maxlen

def DFS(root, cur, target):

if not root: return

if root.val == target:

cur += 1

else:

cur = 1

maxlen = max(cur, maxlen)

DFS(root.left, cur, root.val+1)

DFS(root.right, cur, root.val+1)