Binary Tree Longest Consecutive Sequence
Given the root of a binary tree, return the length of the longest consecutive sequence path.
A consecutive sequence path is a path where the values increase by one along the path.
Note that the path can start at any node in the tree, and you cannot go from a node to its parent in the path.
Example 1:
Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.
Example 2:
Input: root = [2,null,3,2,null,1]
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.
Constraints:
The number of nodes in the tree is in the range [1, 3 * 104].
-3 * 104 ≤ Node.val ≤ 3 * 104
Approach #1 (Top Down Depth-first Search)
A top down approach is similar to an in-order traversal.
We use a variable length to store the current consecutive path length and pass it down the tree.
As we traverse, we compare the current node with its parent node to determine if it is consecutive.
If not, we reset the length.
private int maxLength = 0;
public int longestConsecutive(TreeNode root) {
dfs(root, null, 0);
return maxLength;
}
private void dfs(TreeNode p, TreeNode parent, int length) {
if (p == null) return;
length = (parent != null && p.val == parent.val + 1) ? length + 1 : 1;
maxLength = Math.max(maxLength, length);
dfs(p.left, p, length);
dfs(p.right, p, length);
}
@lightmark presents a neat approach without storing the maxLength as a global variable.
public int longestConsecutive(TreeNode root) {
return dfs(root, null, 0);
}
private int dfs(TreeNode p, TreeNode parent, int length) {
if (p == null) return length;
length = (parent != null && p.val == parent.val + 1) ? length + 1 : 1;
return Math.max(length, Math.max(dfs(p.left, p, length),dfs(p.right, p, length)));
}
Complexity Analysis
Time complexity : O(n).
The time complexity is the same as an in-order traversal of a binary tree with n nodes.
Space complexity : O(n).
The extra space comes from implicit stack space due to recursion.
For a skewed binary tree, the recursion could go up to n levels deep.
