本文主要是介绍LeetCode面试298，二叉树最长连续序列（Python），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
开始想着dfs，两种情况
1.以root为根
2.不以root为根
但是这样需要两个dfs分别进行，那么时间复杂度就上去了。
class Solution:def longestConsecutive(self, root: Optional[TreeNode]) -> int:def dfs(root):# 以root为根节点，可以延续几个点ans = 1if root.left and root.left.val - root.val == 1:ans = max(ans, 1+dfs(root.left))if root.right and root.right.val - root.val == 1:ans = max(ans, 1+dfs(root.right))return ansif not root: return 0ans = dfs(root)ans = max(ans, self.longestConsecutive(root.left), self.longestConsecutive(root.right))return ans题解中提出一种思路可以同时进行dfs，只用把所有节点遍历一遍。
从上到下遍历，建立一个dfs（u, v, length），u为v的父节点，v为u的子节点，length以父节点为最后一个节点的序列长度（初始长度为1）
如果子节点刚好比父节点大1，那么length + 1，反之，length = 1
再继续遍历v的子节点
class Solution:def __init__(self):self.m = 1def longestConsecutive(self, root: Optional[TreeNode]) -> int:self.dfs(root, root, 1)return self.mdef dfs(self, u, v, length):# u为父节点，v为子节点，length为初始长度if not v: return if v.val - u.val == 1:length += 1self.m = max(self.m, length)else:length = 1self.dfs(v, v.left, length)self.dfs(v, v.right, length)
举一反三，还是按照之前的想法，不过只需要改变一点点，只有一种情况：
以root为根的最长序列
如果root.left.val - root.val==1，那么（以root为根的最长序列）可能就等于（以root.left为根的最长序列+1），如果root.right.val - root.val==1，那么（以root为根的最长序列）可能就等于（以root.right为根的最长序列+1），如果都不满足，那么返回1。
怎么有点像列表维护最长序列。其实就可以将链表想象成多方向的列表。
class Solution:def __init__(self):self.m = 1def longestConsecutive(self, root: Optional[TreeNode]) -> int:self.dfs(root)return self.mdef dfs(self, root):if not root:returnl, r = self.dfs(root.left), self.dfs(root.right)if root.left and root.left.val - root.val == 1:l += 1self.m = max(self.m, l)else:l = 0if root.right and root.right.val - root.val == 1:r += 1self.m = max(self.m, r)else:r = 0return max(1, l, r)
这篇关于LeetCode面试298，二叉树最长连续序列（Python）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
