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

给一棵二叉树,找到最长连续路径的长度。
这条路径是指 任何的节点序列中的起始节点到树中的任一节点都必须遵循 父-子 联系。最长的连续路径必须是从父亲节点到孩子节点(不能逆序)。

在线评测地址:领扣题库官网

样例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;
    }
}

更多题解参考:九章官网solution

上一篇:算法面试真题详解: 寻找峰值 II


下一篇:Reinforcement Learning in Continuous State and Action Spaces: A Brief Note