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

给一棵二叉树，找到最长连续路径的长度。
这条路径是指 任何的节点序列中的起始节点到树中的任一节点都必须遵循 父-子 联系。最长的连续路径必须是从父亲节点到孩子节点（不能逆序）。
样例1:
  1. 输入:
  2. {1,#,3,2,4,#,#,#,5}
  3. 输出:3
  4. 说明:
  5. 这棵树如图所示
  6.    1
  7.     \
  8.      3
  9.     / \
  10.    2   4
  11.         \
  12.          5
  13. 最长连续序列是3-4-5，所以返回3.
  14. 样例2:
  15. 输入:
  16. {2,#,3,2,#,1,#}
  17. 输出:2
  18. 说明:
  19. 这棵树如图所示：
  20.    2
  21.     \
  22.      3
  23.     /
  24.    2   
  25.   /
  26. 1
  27. 最长连续序列是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)。
  1. public class Solution {
  2.     /**
  3.      * @param root: the root of binary tree
  4.      * @return: the length of the longest consecutive sequence path
  5.      */
  6.     public int longestConsecutive(TreeNode root) {
  7.         int[] result = helper(root);
  8.         return result[1];
  9.     }
  10.     // 返回以 root 为端点的最长链，和以 root 为根的子树的最长链
  11.     int[] helper(TreeNode root) {
  12.         // 递归出口
  13.         if (root == null) {
  14.             return new int[2];
  15.         }
  16.         int rootMaxLength = 1;
  17.         int subtreeMaxLength = 1;
  18.         
  19.         // 处理左子树的信息
  20.         int[] leftResult = helper(root.left);
  21.         if (root.left != null && root.val + 1 == root.left.val) {
  22.             rootMaxLength = Math.max(rootMaxLength, leftResult[0] + 1);
  23.         }
  24.         subtreeMaxLength = Math.max(subtreeMaxLength, leftResult[1]);
  25.         
  26.         // 处理右子树的信息
  27.         int[] rightResult = helper(root.right);
  28.         if (root.right != null && root.val + 1 == root.right.val) {
  29.             rootMaxLength = Math.max(rootMaxLength, rightResult[0] + 1);
  30.         }
  31.         subtreeMaxLength = Math.max(subtreeMaxLength, rightResult[1]);
  32.         
  33.         // 考虑当前节点为端点的链是子树最长链的情况
  34.         subtreeMaxLength = Math.max(subtreeMaxLength, rootMaxLength);
  35.         
  36.         int[] result = new int[2];
  37.         result[0] = rootMaxLength;
  38.         result[1] = subtreeMaxLength;
  39.         return result;
  40.     }
  41. }
原文：
https://developer.aliyun.com/article/779915?spm=5176.8068049.0.0.55746d19KK8PBG&groupCode=ai