Skip to content

298 Binary Tree Longest Consecutive Sequence

298. Binary Tree Longest Consecutive Sequence

题目: https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

难度 : Medium

思路:

TLE代码,每个node求,然后求最大值

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def longestConsecutive(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def consecutive(root):
            if root == None:
                return 0
            else:
                left, right = 0,0
                if root.left:
                    if root.left.val == root.val + 1:
                        left = 1 + consecutive(root.left)
                if root.right:
                    if root.right.val == root.val + 1:
                        right = 1 + consecutive(root.right)
                return max(left, right, 1)

        def dfs(root):
            s = []
            s.append(root)
            while s:
                root = s.pop()
                res.append(consecutive(root))
                if root.left:
                    s.append(root.left)
                if root.right:
                    s.append(root.right)
        if not root:
            return 0

        res = []
        dfs(root)
        return max(res)

其实第二次递归,也就是dfs其实是有点多余的?因为可以边走边保存最大值?

因为可以

  • recursion,在参数中包含当前的连续seq长度
  • 如果left, right child的value是连续的,那么就将长度+1传入下一个call

AC代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def longestConsecutive(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(root, curLen):
            self.result = max(curLen, self.result)
            if root.left:
                if root.left.val == root.val + 1:
                    dfs(root.left, curLen + 1)
                else:
                    dfs(root.left, 1)
            if root.right:
                if root.right.val == root.val + 1:
                    dfs(root.right, curLen + 1)
                else:
                    dfs(root.right,1)

        if not root: return 0

        self.result = 0
        dfs(root, 1)
        return self.result

这里值得注意的是这里的self.result其实相当于dfs的全局变量,也是利用了这个才做到边递归边记录边重置。



回到顶部