# 549. Binary Tree Longest Consecutive Sequence II
Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.
Especially, this path can be either increasing or decreasing. For example, [1,2,3,4]
and [4,3,2,1]
are both considered valid, but the path [1,2,4,3]
is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.
Example 1:
Input:
1
/ \
2 3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].
Example 2:
Input:
2
/ \
1 3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].
# Solution
Approach 1: returns (max_increasing, max_decreasing) for path through root while keeping a global max.
# Code (Python)
Approach 1: (not verified on leetcode)
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def longest_consecutive(root):
max_length = [1]
_explore(root, max_length)
return max_length[0]
def _explore(root, max_length):
# returns (max_increasing, max_decreasing) for path through root
if not root:
return (0, 0)
left_increasing, left_decreasing = _explore(root.left, max_length)
right_increasing, right_decreasing = _explore(root.right, max_length)
increasing, decreasing = 1, 1
if root.left:
if root.left.val + 1 == root.val:
decreasing += left_decreasing
if root.left.val - 1 == root.val:
increasing += left_increasing
if root.right:
if root.right.val + 1 == root.val:
decreasing = max(decreasing, right_decreasing + 1)
if root.right.val - 1 == root.val:
increasing = max(increasing, right_increasing + 1)
max_length[0] = max(max_length[0], increasing, decreasing)
if root.left and root.right:
if root.left.val + 1 == root.val == root.right.val - 1:
max_length[0] = max(max_length[0], left_decreasing + 1 + right_increasing)
if root.right.val + 1 == root.val == root.left.val - 1:
max_length[0] = max(max_length[0], left_increasing + 1 + right_decreasing)
return (increasing, decreasing)
node = TreeNode(2, TreeNode(1), TreeNode(3))
root = TreeNode(5, node, TreeNode(6))
print(longest_consecutive(root))
Approach 2:
# Code (C++)
Approach 1:
Approach 2: