LeetCode 298 Binary Tree Longest Consecutive Sequence

LeetCode

Given the root of a binary tree, return 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 needs to be from parent to child (cannot be the reverse).

Example 1:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input: root = [2,null,3,2,null,1]
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

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>`

题目大意：

求从父到子的最长连续数列的长度(由小到大)

解题思路：

DFS

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

解题步骤：

N/A

注意事项：

1. 题意是从父到儿子的有小到大数列，而不是儿子到父亲
2. 以root为起点的最长数列，若root不符合条件，不加入left或right的长度
3. 类似于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
		nonlocal max_len
		lpath = rpath = 1
		left = dfs(root.left)
		right = dfs(root.right)
		if root.left and root.val + 1 == root.left.val:  # remember not ==
			lpath += left
		if root.right and root.val + 1 == root.right.val:
			rpath += right
		res = max(lpath, rpath)
		max_len = max(res, max_len)
		return res

	dfs(root)
	return max_len

算法分析：

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