## 题目描述：

LeetCode 549. Binary Tree Longest Consecutive Sequence II

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, 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:
1
/ \
2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].
```

Example 2:

```Input:
2
/ \
1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].
```

## 解题思路：

```定义函数solve(root)，递归求解以root为根节点向子节点方向（parent-child）的路径中，最大连续递增路径长度inc，以及最大连续递减路径长度dec

## Python代码：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def solve(self, root):
inc = dec = 0
for child in (root.left, root.right):
if not child: continue
cinc, cdec = self.solve(child)
if child.val == root.val - 1:
dec = max(dec, cdec)
elif child.val == root.val + 1:
inc = max(inc, cinc)
self.ans = max(self.ans, inc + dec + 1)
return inc + 1, dec + 1

def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
if root: self.solve(root)
return self.ans
``````

```定义函数maxLength，递归计算从根节点出发向叶子节点可以得到的最长连续路径长度。

## Python代码：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def maxLength(self, root, val, delta):
lchild, rchild = root.left, root.right
lsize = rsize = 0
if lchild and lchild.val == val + delta:
lsize = self.maxLength(lchild, val + delta, delta)
if rchild and rchild.val == val + delta:
rsize = self.maxLength(rchild, val + delta, delta)
return 1 + max(lsize, rsize)

def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
lchild, rchild = root.left, root.right
lsize = rsize = 0
clen = 1
if lchild and abs(lchild.val - root.val) == 1:
lsize = self.maxLength(lchild, lchild.val, lchild.val - root.val)
if rchild and abs(rchild.val - root.val) == 1:
rsize = self.maxLength(rchild, rchild.val, rchild.val - root.val)
if lchild and rchild and lchild.val != rchild.val:
clen += lsize + rsize
else:
clen += max(lsize, rsize)
llen = self.longestConsecutive(lchild)
rlen = self.longestConsecutive(rchild)
return max(clen, llen, rlen)
``````

```定义函数findPath，递归寻找从根节点出发向叶子节点可以得到的最长连续路径。

## Python代码：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findPath(self, root, val, delta):
lchild, rchild = root.left, root.right
lpath = rpath = []
if lchild and lchild.val == val + delta:
lpath = self.findPath(lchild, val + delta, delta)
if rchild and rchild.val == val + delta:
rpath = self.findPath(rchild, val + delta, delta)
return [val] + max(lpath, rpath)

def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
lchild, rchild = root.left, root.right
lpath = rpath = []
clen = 1
if lchild and abs(lchild.val - root.val) == 1:
lpath = self.findPath(lchild, lchild.val, lchild.val - root.val)
if rchild and abs(rchild.val - root.val) == 1:
rpath = self.findPath(rchild, rchild.val, rchild.val - root.val)
if lchild and rchild and lchild.val != rchild.val:
clen += len(lpath) + len(rpath)
else:
clen += max(len(lpath), len(rpath))
llen = self.longestConsecutive(lchild)
rlen = self.longestConsecutive(rchild)
return max(clen, llen, rlen)``````

Pingbacks已关闭。