[LeetCode] 549. Binary Tree Longest Consecutive Sequence II 二叉树最长连续序列之 II

2021年09月15日 阅读数：1

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.html

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.java

Example 1:node

```Input:
1
/ \
2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].```

Example 2:python

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

128. Longest Consecutive Sequence 的拓展，仍是找最长的连续序列，这一题里能够是升序也能够是降序，并且没必要从父结点到子结点，能够子父子节点。ide

Compared with 298. Binary Tree Longest Consecutive Sequence, this question includes more different conditions since it allows for:url

1. both increasing and decreasing order from a follows the parent-child path.
2. child-parent-child path.

Hence this question actually contains 2 subproblems to solve:code

1. what is the longest increasing consecutive parent-child path sequence given a `root` node?
2. what is the longest decreasing consecutive parent-child path sequence given a `root` node?

Based on the above 2 sub-solution, we know that the longest consecutive sequence for a given `root` is `longest_increasing_sequence + longest_decreasing_sequence` from this `root`. We can simply add up this 2 value because the longest increasing consecutive sequence and longest decreasing consecutive sequence is guaranteed to showed up in different child path (otherwise there will be a contradiction--a child's value cannot be greater than and less than the root's value at the same time).

If the root's value's value is not consecutive with a child's value, then the length of current sequence is simply 1.

Time complexity: `O(n)` where `n` is the number of nodes in the tree.

Space complexity: `O(logn)` on average for the recursion stack since this is a binary tree.

Java:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
int max = 0;
public int longestConsecutive(TreeNode root) {
getLongestConsecutive(root);
return max;
}

private int[] getLongestConsecutive(TreeNode root) {
// returns [longest_decreasing_length_from_root, longest_increasing_length_from_root]
if (root == null) return new int[]{0, 0};
int[] left = getLongestConsecutive(root.left);
int[] right = getLongestConsecutive(root.right);
int dcr = 1, icr = 1;
if (root.left != null) {
if (root.left.val == root.val + 1) {
icr = left[1] + 1;
}
if (root.left.val == root.val - 1) {
dcr = left[0] + 1;
}
}
if (root.right != null) {
if (root.right.val == root.val + 1) {
icr = Math.max(icr, right[1] + 1);
} if (root.right.val == root.val - 1) {
dcr = Math.max(dcr, right[0] + 1);
}
}
max = Math.max(max, dcr + icr - 1);
return new int[]{dcr, icr};
}
}　　```

Python:

```# Time:  O(n)
# Space: O(h)
class Solution(object):
def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def longestConsecutiveHelper(root):
if not root:
return 0, 0
left_len = longestConsecutiveHelper(root.left)
right_len = longestConsecutiveHelper(root.right)
cur_inc_len, cur_dec_len = 1, 1
if root.left:
if root.left.val == root.val + 1:
cur_inc_len = max(cur_inc_len, left_len[0] + 1)
elif root.left.val == root.val - 1:
cur_dec_len = max(cur_dec_len, left_len[1] + 1)
if root.right:
if root.right.val == root.val + 1:
cur_inc_len = max(cur_inc_len, right_len[0] + 1)
elif root.right.val == root.val - 1:
cur_dec_len = max(cur_dec_len, right_len[1] + 1)
self.max_len = max(self.max_len, cur_dec_len + cur_inc_len - 1)
return cur_inc_len, cur_dec_len

self.max_len = 0
longestConsecutiveHelper(root)
return self.max_len
```

Python: 一次遍历

```class Solution(object):
def solve(self, root):
inc = dec = 0
for child in (root.left, root.right):
if not child: continue
cinc, cdec = self.solve(child)
if child.val == root.val - 1:
dec = max(dec, cdec)
elif child.val == root.val + 1:
inc = max(inc, cinc)
self.ans = max(self.ans, inc + dec + 1)
return inc + 1, dec + 1

def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
if root: self.solve(root)
return self.ans
```

Python: 递归 + 遍历二叉树, Time: O(n^2)

```class Solution(object):
def maxLength(self, root, val, delta):
lchild, rchild = root.left, root.right
lsize = rsize = 0
if lchild and lchild.val == val + delta:
lsize = self.maxLength(lchild, val + delta, delta)
if rchild and rchild.val == val + delta:
rsize = self.maxLength(rchild, val + delta, delta)
return 1 + max(lsize, rsize)

def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
lchild, rchild = root.left, root.right
lsize = rsize = 0
clen = 1
if lchild and abs(lchild.val - root.val) == 1:
lsize = self.maxLength(lchild, lchild.val, lchild.val - root.val)
if rchild and abs(rchild.val - root.val) == 1:
rsize = self.maxLength(rchild, rchild.val, rchild.val - root.val)
if lchild and rchild and lchild.val != rchild.val:
clen += lsize + rsize
else:
clen += max(lsize, rsize)
llen = self.longestConsecutive(lchild)
rlen = self.longestConsecutive(rchild)
return max(clen, llen, rlen)
```

C++:

```// Time:  O(n)
// Space: O(h)

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int longestConsecutive(TreeNode* root) {
int max_len = 0;
longestConsecutiveHelper(root, &max_len);
return max_len;
}

pair<int, int> longestConsecutiveHelper(TreeNode *root, int *max_len) {
if (!root) {
return {0, 0};
}
const pair<int, int> left_len = longestConsecutiveHelper(root->left, max_len);
const pair<int, int> right_len = longestConsecutiveHelper(root->right, max_len);

int cur_inc_len = 1, cur_dec_len = 1;
if (root->left) {
if (root->left->val == root->val + 1) {
cur_inc_len = max(cur_inc_len, left_len.first + 1);
} else if (root->left->val == root->val - 1){
cur_dec_len = max(cur_dec_len, left_len.second + 1);
}
}
if (root->right) {
if (root->right->val == root->val + 1) {
cur_inc_len = max(cur_inc_len, right_len.first + 1);
} else if (root->right->val == root->val - 1) {
cur_dec_len = max(cur_dec_len, right_len.second + 1);
}
}
*max_len = max(*max_len, cur_dec_len + cur_inc_len - 1);
return {cur_inc_len, cur_dec_len};
}
};
```

C++:

```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};
}
};
```

C++:

```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);
}
};
```

[LeetCode] 298. Binary Tree Longest Consecutive Sequence 二叉树最长连续序列

[LeetCode] 128. Longest Consecutive Sequence 求最长连续序列

[LeetCode] 300. Longest Increasing Subsequence 最长递增子序列

[LintCode] 619 Binary Tree Longest Consecutive Sequence III 二叉树最长连续序列 III