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
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
Algorithm
\nA 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;\npublic int longestConsecutive(TreeNode root) {\n dfs(root, null, 0);\n return maxLength;\n}\n\nprivate void dfs(TreeNode p, TreeNode parent, int length) {\n if (p == null) return;\n length = (parent != null && p.val == parent.val + 1) ? length + 1 : 1;\n maxLength = Math.max(maxLength, length);\n dfs(p.left, p, length);\n dfs(p.right, p, length);\n}\n
@lightmark presents a neat approach without storing the maxLength as a global variable.
\npublic int longestConsecutive(TreeNode root) {\n return dfs(root, null, 0);\n}\n\nprivate int dfs(TreeNode p, TreeNode parent, int length) {\n if (p == null) return length;\n length = (parent != null && p.val == parent.val + 1) ? length + 1 : 1;\n return Math.max(length, Math.max(dfs(p.left, p, length),\n dfs(p.right, p, length)));\n}\n
Complexity analysis
\nTime complexity : .\nThe time complexity is the same as an in-order traversal of a binary tree with nodes.
\nSpace complexity : .\nThe extra space comes from implicit stack space due to recursion. For a skewed binary tree, the recursion could go up to levels deep.
\nAlgorithm
\nThe bottom-up approach is similar to a post-order traversal. We return the consecutive path length starting at current node to its parent. Then its parent can examine if its node value can be included in this consecutive path.
\nprivate int maxLength = 0;\npublic int longestConsecutive(TreeNode root) {\n dfs(root);\n return maxLength;\n}\n\nprivate int dfs(TreeNode p) {\n if (p == null) return 0;\n int L = dfs(p.left) + 1;\n int R = dfs(p.right) + 1;\n if (p.left != null && p.val + 1 != p.left.val) {\n L = 1;\n }\n if (p.right != null && p.val + 1 != p.right.val) {\n R = 1;\n }\n int length = Math.max(L, R);\n maxLength = Math.max(maxLength, length);\n return length;\n}\n
Complexity analysis
\nTime complexity : .\nThe time complexity is the same as a post-order traversal in a binary tree, which is .
\nSpace complexity : .\nThe extra space comes from implicit stack space due to recursion. For a skewed binary tree, the recursion could go up to levels deep.
\n