Create binary_tree_longest_consecutive_sequence.py

yingl · web-flow · commit 5089cb0c4bb6 · 2019-04-25T15:58:36.000+08:00
diff --git a/binary_tree_longest_consecutive_sequence.py b/binary_tree_longest_consecutive_sequence.py
@@ -0,0 +1,22 @@
+class Solution:
+    """
+    @param root: the root of binary tree
+    @return: the length of the longest consecutive sequence path
+    """
+    def longestConsecutive(self, root):
+        # write your code here
+        return Solution.longest(root, None, 0)
+
+    @staticmethod
+    def longest(node, parent, curr_len):
+        if not node:
+            return 0
+        if parent and ((parent.val + 1) == node.val):
+            curr_len = curr_len + 1
+        else:
+            curr_len = 1
+        left_len = Solution.longest(node.left, node, curr_len)
+        right_len = Solution.longest(node.right, node, curr_len)
+        return max(curr_len, max(left_len, right_len))
+        
+# easy: https://www.lintcode.com/problem/binary-tree-longest-consecutive-sequence/
