LeetCode 549 Binary Tree Longest Consecutive Sequence II

LeetCode

Given the root of a binary tree, return the length of the longest consecutive path in the tree.

A consecutive path is a path where the values of the consecutive nodes in the path differ by one. This path can be either increasing or decreasing.

For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid.

On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input: root = [1,2,3]
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input: root = [2,1,3]
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Constraints: The number of nodes in the tree is in the range [1, 3 * 10<sup>4</sup>].
`-3 10<sup>4</sup> <= Node.val <= 3 * 10<sup>4</sup>`

题目大意：

求任意节点到另一个节点的最长连续数列的长度(由小到大)

解题思路：

类似于LeetCode 298 Binary Tree Longest Consecutive Sequence，不过由于父亲到儿子可能递增或递减，所以DFS返回值也返回递增和递减的长度

LeetCode 298 Binary Tree Longest Consecutive Sequence 父亲到儿子由小到大
LeetCode 549 Binary Tree Longest Consecutive Sequence II 任一节点到另一个节点由小到大

类似于LeetCode 124 Binary Tree Maximum Path Sum，有四种情况：自己，自己+左，自己+右，左+右

解题步骤：

N/A

注意事项：

1. DFS返回值也返回递增和递减的长度
2. 类似于LeetCode 124 Binary Tree Maximum Path Sum，有四种情况：自己，自己+左，自己+右，左+右

Python代码：

def longestConsecutive(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0, 0  # (increasing, decreasing) from root
		nonlocal max_len
		inc = desc = 1
		lpath = rpath = 1
		left = dfs(root.left)
		right = dfs(root.right)
		if root.left and root.val + 1 == root.left.val:
			lpath += left[0]
		if root.right and root.val + 1 == root.right.val:
			rpath += right[0]
		inc = max(1, lpath, rpath)

		lpath = rpath = 1
		if root.left and root.val - 1 == root.left.val:
			lpath += left[1]
		if root.right and root.val - 1 == root.right.val:
			rpath += right[1]
		desc = max(1, lpath, rpath)

		total = inc + desc - 1
		max_len = max(inc, desc, total, max_len)
		return inc, desc

	dfs(root)
	return max_len

算法分析：

时间复杂度为O(n)，空间复杂度O(1)