评论算法,在二叉树中找到最长的连续序列的问题,可以使用深度优先搜索(DFS)来解决。
首先,我们需要定义一个辅助函数,该函数将递归地遍历二叉树的每个节点,并返回以当前节点为起点的最长连续序列的长度。
具体步骤如下:
最后,调用辅助函数findLongestConsecutive(root, None, 0),即可得到二叉树中最长的连续序列的长度。
以下是一个示例的Python实现:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findLongestConsecutive(root):
if not root:
return 0
max_length = 0
def dfs(node, parent_val, length):
nonlocal max_length
if not node:
return 0
if parent_val is not None and node.val == parent_val + 1:
length += 1
else:
length = 1
max_length = max(max_length, length)
dfs(node.left, node.val, length)
dfs(node.right, node.val, length)
dfs(root, None, 0)
return max_length
# 示例用法
root = TreeNode(1)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(5)
result = findLongestConsecutive(root)
print(result) # 输出:3
在这个示例中,我们构建了一个二叉树,并调用findLongestConsecutive函数来找到最长的连续序列,结果为3。
领取专属 10元无门槛券
手把手带您无忧上云