九章算法 | Google 面试题：二叉树最长连续序列

给一棵二叉树，找到最长连续路径的长度。

这条路径是指 任何的节点序列中的起始节点到树中的任一节点都必须遵循 父-子 联系。最长的连续路径必须是从父亲节点到孩子节点（​不能逆序​）。

在线评测地址：LintCode

样例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.

解题思路

本题在二叉树遍历的基础上，统计树上的信息，可以用深度优先搜索递归解决。每次统计完某个节点为端点最长链和子树中最长链的信息，并返回父节点，这样自底向上进行计算。如果某个节点能和子节点组成链，那么它能组成的最长链为子节点能组成的最长链长度加上一。

代码思路

递归步骤：

1. 如果节点为空，返回​(0, 0)​。
2. 令​rootMaxLength = 1​，代表该节点的最长链长度。
3. 令​subtreeMaxLength = 1​，代表子树最长链长度。
4. 递归获得左子树信息leftResult，更新​rootMaxLength​和​subMaxLength​。
5. 递归获得右子树信息rightResult，更新​rootMaxLength​和​subMaxLength​。
6. 返回​(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;
    }
}

更多题解参考：九章算法