Python 二叉树最长连续序列
二叉树最长连续序列是指在二叉树中找到最长的连续元素序列。连续元素序列指的是节点的值连续递增1的情况。
例如,对于下面这棵二叉树:
1
\
3
/ \
2 4
\
5
最长连续序列为3,即1->2->3。
思路分析
要找出二叉树中的最长连续序列,可以采用深度优先搜索(DFS)的方法。我们可以写一个递归函数,从根节点开始遍历二叉树,不断更新当前连续序列的长度,并返回最长的连续序列长度。
具体来说,对于每个节点,我们需要考虑三种情况:
1. 如果当前节点为空,直接返回0。
2. 如果当前节点的值与其父节点值相差1,说明当前节点可以加入到当前连续序列中,否则当前连续序列长度置为1。
3. 递归遍历当前节点的左右子树,更新当前连续序列的长度。
最后,返回左右子树中最长的连续序列长度即可。
代码实现
下面是用Python实现的代码:
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):
if not root:
return 0
self.res = 0
def helper(node, parent_val, length):
if not node:
return
if node.val == parent_val + 1:
length += 1
else:
length = 1
self.res = max(self.res, length)
helper(node.left, node.val, length)
helper(node.right, node.val, length)
helper(root, root.val, 0)
return self.res
运行示例
接下来我们用上面的代码来测试一下,构建一个示例:
# 构建二叉树
root = TreeNode(1)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(5)
# 实例化Solution类
s = Solution()
print(s.longestConsecutive(root)) # 输出:3
在上面的示例中,我们构建了一棵包含5个节点的二叉树,然后计算得到最长的连续序列长度为3。
通过以上代码和分析,我们可以得出二叉树最长连续序列的解法。