# 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].
``````

Note: All the values of tree nodes are in the range of [-1e7, 1e7].

``````class Solution {
public:
int longestConsecutive(TreeNode* root) {
int res = 0;
helper(root, root, res);
return res;
}
pair<int, int> helper(TreeNode* node, TreeNode* parent, int& res) {
if (!node) return {0, 0};
auto left = helper(node->left, node, res);
auto right = helper(node->right, node, res);
res = max(res, left.first + right.second + 1);
res = max(res, left.second + right.first + 1);
int inc = 0, dec = 0;
if (node->val == parent->val + 1) {
inc = max(left.first, right.first) + 1;
} else if (node->val + 1 == parent->val) {
dec = max(left.second, right.second) + 1;
}
return {inc, dec};
}
};
``````

``````class Solution {
public:
int longestConsecutive(TreeNode* root) {
if (!root) return 0;
int res = helper(root, 1) + helper(root, -1) + 1;
return max(res, max(longestConsecutive(root->left), longestConsecutive(root->right)));
}
int helper(TreeNode* node, int diff) {
if (!node) return 0;
int left = 0, right = 0;
if (node->left && node->val - node->left->val == diff) {
left = 1 + helper(node->left, diff);
}
if (node->right && node->val - node->right->val == diff) {
right = 1 + helper(node->right, diff);
}
return max(left, right);
}
};
``````

Binary Tree Longest Consecutive Sequence

https://discuss.leetcode.com/topic/85808/c-solution

https://discuss.leetcode.com/topic/85778/dfs-c-python-solutions

https://discuss.leetcode.com/topic/85764/neat-java-solution-single-pass-o-n

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation