595 · 二叉树最长连续序列 - LintCode

Difficulty
easy
Tags
二叉树
URL
https://www.lintcode.com/problem/595
Star
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
Wechat reply the【BAT】get the latest frequent Interview questions of ByteDance, Alibaba, etc. (wechat id :jiuzhang15)
Example 1:
Input:
   1
    \
     3
    / \
   2   4
        \
         5
Output:3
Explanation:
Longest consecutive sequence path is 3-4-5, so return 3.
Example 2:
Input:
   2
    \
     3
    /
   2
  /
 1
Output:2
Explanation:
Longest consecutive sequence path is 2-3,not 3-2-1, so return 2.

法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_consecutive(self, root: TreeNode) -> int:
        # write your code here
        self.res = 1
        self.dfs(root=root, pre_val=None, length=0)
        return self.res


    def dfs(self, root, pre_val, length):
        if root is None:
            return 
			
        if pre_val and pre_val + 1 == root.val:
            temp = length + 1
        else:
            temp = 1
        self.res = max(self.res, temp)

        self.dfs(root.left, root.val, temp)
        self.dfs(root.right, root.val, temp)