0549：二叉树中最长的连续序列（★）

2016-07-02 约 342 字预计阅读 1 分钟次阅读

力扣第 549 题

题目

给定二叉树的根 root ，返回树中最长连续路径的长度。
连续路径是路径中相邻节点的值相差 1 的路径。此路径可以是增加或减少。

例如， [1,2,3,4] 和 [4,3,2,1] 都被认为有效，但路径 [1,2,4,3] 无效。

另一方面，路径可以是子-父-子顺序，不一定是父子顺序。

示例 1:

输入: root = [1,2,3]
输出: 2
解释: 最长的连续路径是 [1, 2] 或者 [2, 1]。

示例 2:

输入: root = [2,1,3]
输出: 3
解释: 最长的连续路径是 [1, 2, 3] 或者 [3, 2, 1]。

提示：

树上所有节点的值都在 [1, 3 * 10⁴] 范围内。
-3 * 10⁴ <= Node.val <= 3 * 10⁴

分析

令 dfs(u) 返回 u 结尾的最长递增/减连续路径，即可递归。同时在递归过程中，可求得经过 u 的最长连续路径。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


def longestConsecutive(self, root: Optional[TreeNode]) -> int:
	def dfs(u):
		if not u:
			return 0,0
		l1,l2 = dfs(u.left)
		r1,r2 = dfs(u.right)
		a = 1+l1 if l1 and u.val==u.left.val+1 else 1
		b = 1+r1 if r1 and u.val==u.right.val+1 else 1
		c = 1+l2 if l2 and u.val==u.left.val-1 else 1
		d = 1+r2 if r2 and u.val==u.right.val-1 else 1
		self.res = max(self.res,a+d-1,b+c-1)
		return max(a,b), max(c,d)
	
	self.res = 0
	dfs(root)
	return self.res

52 ms

目录

0549：二叉树中最长的连续序列（★）

题目

分析

解答