难度: Medium
Submission
运行时间: 35 ms
内存: 17.4 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: TreeNode) -> int:
def dfs(root):
if root is None:
return [0, 0]
nonlocal ans
incr = decr = 1
i1, d1 = dfs(root.left)
i2, d2 = dfs(root.right)
if root.left:
if root.left.val + 1 == root.val:
incr = i1 + 1
if root.left.val - 1 == root.val:
decr = d1 + 1
if root.right:
if root.right.val + 1 == root.val:
incr = max(incr, i2 + 1)
if root.right.val - 1 == root.val:
decr = max(decr, d2 + 1)
ans = max(ans, incr + decr - 1)
return [incr, decr]
ans = 0
dfs(root)
return ans
Explain
这个题解使用递归的深度优先搜索（DFS）来遍历二叉树。对于每个节点，分别递归遍历其左右子树，返回两个值：从该节点开始向下递增序列的长度和向下递减序列的长度。在遍历过程中，根据当前节点与其左右子节点的值的关系，更新向下递增序列和向下递减序列的长度，并记录最长连续序列的长度。最终返回整棵树中最长连续序列的长度。
时间复杂度: 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: TreeNode) -> int:
def dfs(root):
if root is None:
return [0, 0]
nonlocal ans
incr = decr = 1
i1, d1 = dfs(root.left) # 递归遍历左子树
i2, d2 = dfs(root.right) # 递归遍历右子树
if root.left:
if root.left.val + 1 == root.val: # 如果当前节点的值比左子节点大1，更新递增序列长度
incr = i1 + 1
if root.left.val - 1 == root.val: # 如果当前节点的值比左子节点小1，更新递减序列长度
decr = d1 + 1
if root.right:
if root.right.val + 1 == root.val: # 如果当前节点的值比右子节点大1，更新递增序列长度
incr = max(incr, i2 + 1)
if root.right.val - 1 == root.val: # 如果当前节点的值比右子节点小1，更新递减序列长度
decr = max(decr, d2 + 1)
ans = max(ans, incr + decr - 1) # 更新最长连续序列的长度
return [incr, decr] # 返回当前节点的递增序列长度和递减序列长度
ans = 0
dfs(root) # 递归遍历整棵二叉树
return ans # 返回最长连续序列的长度
Explore
当一个节点没有左右子节点时，该节点本身可以视为一个长度为1的连续序列。因此，无论是从该节点开始的递增序列还是递减序列，长度都是1，因为没有其他节点可以与之形成更长的连续序列。
如果当前节点的子节点值与当前节点的值差不是1，那么这个子节点不会与当前节点形成连续的递增或递减序列。在这种情况下，当前节点的递增或递减序列长度不会被子节点的相应序列值影响，它们保持为1，即仅包括当前节点自身。
使用`max`函数是为了确定从当前节点开始向下的最长递增或递减序列。由于左子树和右子树可能分别形成不同长度的连续序列，因此我们需要选择左右子树中更长的一个序列来与当前节点形成更长的连续序列。
当计算包括当前节点在内的最长连续序列时，`incr`代表向下递增序列的长度，`decr`代表向下递减序列的长度。由于这两个序列都包含当前节点，因此在将它们相加时会重复计算当前节点。为了得到正确的序列总长度，需要从总和中减去1，以去除这种重复计数。