算法面试真题详解：二叉树最长连续序列

给一棵二叉树，找到最长连续路径的长度。
这条路径是指 任何的节点序列中的起始节点到树中的任一节点都必须遵循 父-子 联系。最长的连续路径必须是从父亲节点到孩子节点（不能逆序）。
样例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;
  •     }
  • }
  • 复制代码
    原文：
    https://developer.aliyun.com/article/779915?spm=5176.8068049.0.0.55746d19KK8PBG&groupCode=ai