难度: Medium
Submission
运行时间: 43 ms
内存: 20.0 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
if not root: return 0
self.max_cnt = 1
def tra(root, pre_node, cnt):
if not root: return
if pre_node and root.val - pre_node.val == 1:
cnt +=1
self.max_cnt = max(cnt, self.max_cnt)
else:
cnt = 1
tra(root.left, root, cnt)
tra(root.right, root, cnt)
tra(root, None, 0)
return self.max_cnt
Explain
这道题使用递归的方式对二叉树进行深度优先搜索。从根节点开始，递归遍历左右子树，同时记录当前连续序列的长度。如果当前节点的值比前一个节点的值大1，则将连续序列长度加1，并更新最长连续序列长度；否则，重置连续序列长度为1。递归结束后，返回最长连续序列的长度。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
if not root: return 0
self.max_cnt = 1
def tra(root, pre_node, cnt):
if not root: return
# 如果当前节点的值比前一个节点的值大1，连续序列长度加1
if pre_node and root.val - pre_node.val == 1:
cnt +=1
self.max_cnt = max(cnt, self.max_cnt)
else:
# 否则，重置连续序列长度为1
cnt = 1
# 递归遍历左子树
tra(root.left, root, cnt)
# 递归遍历右子树
tra(root.right, root, cnt)
tra(root, None, 0)
return self.max_cnt
Explore
是的，`pre_node`参数在算法中起到关键作用，主要用于记录当前节点的前一个节点。这样，每次递归调用时，可以通过比较当前节点的值和前一个节点的值来确定是否当前节点继续形成连续递增序列。如果当前节点的值正好比前一个节点的值大1，则连续序列长度增加；否则，连续序列长度重置为1。这是实现二叉树最长连续序列问题的核心逻辑。
在当前的算法实现中，如果二叉树中的连续节点具有相同的值，这些节点不会被计算为连续递增的一部分。算法只考虑值严格递增的情形，即当前节点的值必须比前一个节点的值大1。因此，如果两个连续的节点值相同，连续序列的长度会被重置为1。这意味着重复值打断了连续递增序列的计算。
该算法主要关注局部的父子关系顺序以确定值是否连续递增。它不需要考虑二叉树节点值的整体顺序。即使子树的根节点值比其父节点小，只要子树内部的节点值连续递增，这些节点仍然被计算为一部分连续序列。算法的设计确保了只要节点之间的值满足连续递增，就可以形成有效的连续序列，不受整体树结构的影响。
此设计确实意味着每次当节点的值没有形成递增序列时，算法会重置连续序列的长度为1，并从当前节点开始尝试形成新的连续序列。然而，通过全局变量`max_cnt`的使用，算法仍然能保持跟踪并更新整个树中观察到的最长连续序列长度。因此，尽管连续序列长度在局部被重置，算法仍然能够从整个二叉树中找到最长的连续递增序列。