给一棵二叉树,找到最长连续路径的长度。
这条路径是指 任何的节点序列中的起始节点到树中的任一节点都必须遵循 父-子 联系。最长的连续路径必须是从父亲节点到孩子节点(不能逆序)。
在线评测地址:领扣题库官网
样例1:
输入:
{1,#,3,2,4,#,#,#,5}
输出:3
说明:
这棵树如图所示
1
\
3
/ \
2 4
\
5
最长连续序列是3-4-5,所以返回3.
样例2:
输入:
{2,#,3,2,#,1,#}
输出:2
说明:
这棵树如图所示:
2
\
3
/
2
/
1
最长连续序列是2-3,而不是3-2-1,所以返回2.
解题思路
本题在二叉树遍历的基础上,统计树上的信息,可以用深度优先搜索递归解决。每次统计完某个节点为端点最长链和子树中最长链的信息,并返回父节点,这样自底向上进行计算。如果某个节点能和子节点组成链,那么它能组成的最长链为子节点能组成的最长链长度加上一。
代码思路
递归步骤:
- 如果节点为空,返回(0, 0)。
- 令rootMaxLength = 1,代表该节点的最长链长度。
- 令subtreeMaxLength = 1,代表子树最长链长度。
- 递归获得左子树信息leftResult,更新rootMaxLength和subMaxLength。
- 递归获得右子树信息rightResult,更新rootMaxLength和subMaxLength。
- 返回(rootMaxLength, subMaxLength)。
复杂度分析
设V为二叉树的节点数。
-
时间复杂度
- 每个节点被遍历1遍,时间复杂度为O(N)。
-
空间复杂度
- 递归遍历二叉树的空间开销取决于二叉树的深度,最劣情况树是一条链,所以时间复杂度为O(N)。
public class Solution {
/**
* @param root: the root of binary tree
* @return: the length of the longest consecutive sequence path
*/
public int longestConsecutive(TreeNode root) {
int[] result = helper(root);
return result[1];
}
// 返回以 root 为端点的最长链,和以 root 为根的子树的最长链
int[] helper(TreeNode root) {
// 递归出口
if (root == null) {
return new int[2];
}
int rootMaxLength = 1;
int subtreeMaxLength = 1;
// 处理左子树的信息
int[] leftResult = helper(root.left);
if (root.left != null && root.val + 1 == root.left.val) {
rootMaxLength = Math.max(rootMaxLength, leftResult[0] + 1);
}
subtreeMaxLength = Math.max(subtreeMaxLength, leftResult[1]);
// 处理右子树的信息
int[] rightResult = helper(root.right);
if (root.right != null && root.val + 1 == root.right.val) {
rootMaxLength = Math.max(rootMaxLength, rightResult[0] + 1);
}
subtreeMaxLength = Math.max(subtreeMaxLength, rightResult[1]);
// 考虑当前节点为端点的链是子树最长链的情况
subtreeMaxLength = Math.max(subtreeMaxLength, rootMaxLength);
int[] result = new int[2];
result[0] = rootMaxLength;
result[1] = subtreeMaxLength;
return result;
}
}
更多题解参考:九章官网solution