Python 二叉树最长连续序列|极客教程

Python 二叉树最长连续序列

二叉树最长连续序列是指在二叉树中找到最长的连续元素序列。连续元素序列指的是节点的值连续递增1的情况。

例如，对于下面这棵二叉树：

最长连续序列为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