614 · 二叉树的最长连续子序列 II - LintCode

Difficulty
Medium
Tags
二叉树
URL
https://www.lintcode.com/problem/614
Star
描述
给定一棵二叉树，找到最长连续序列(单调且相邻节点值相差为1)路径的长度(节点数)。路径起点跟终点可以为二叉树的任意节点。
样例
例1:
输入:
{1,2,0,3}
输出:
4
解释:
    1
   / \
  2   0
 /
3
0-1-2-3
例2:
输入:
{3,2,2}
输出:
2
解释:
    3
   / \
  2   2
2-3

法 1 信息传递

思路
题解
from lintcode import (
    TreeNode,
)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the length of the longest consecutive sequence path
    """
    def longest_consecutive2(self, root: TreeNode) -> int:
        # write your code here
        self.res = 0
        self.helper(root)
        return self.res

    def helper(self, root):
        if root is None:
            # {递减，递增}
            return [0, 0]

        l = self.helper(root.left)
        r = self.helper(root.right)

        inr = 1  # 表示递增的序列长度  递增递减是从左往右看的
        dcr = 1  # 表示递减的序列长度
        if root.left:
            if root.val == root.left.val + 1:
                inr= l[0] + 1
            elif root.val == root.left.val - 1:
                dcr = l[1] + 1

        if root.right:
            if root.val == root.right.val + 1:
                inr= max(inr, r[0]+1)
            elif root.val == root.right.val - 1:
                dcr = max(dcr, r[1]+1)

        self.res = max(self.res, dcr + inr - 1)

        return [inr, dcr]