298._Binary_Tree_Longest_Consecutive_Sequence.md

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的全局变量，也是利用了这个才做到边递归边记录边重置。