Osheep

时光不回头,当下最重要。

Leetcode 124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,
1
/ |
2 3
Return 6.

题意:求一个二叉树的一条最大路径和,这条路径可以从任意节点起始,到任意节点结束,但至少要有一个节点。

思路:
如例子,路径总共有三种类型:[1,2],[1,3],[2,1,3]。
即每个节点可以连接它的左边一条最大路径,或连接右边一条最大路径,或把左右最大路径连接起来。
因此我想到,用一个方法求以当前节点为起始节点,到它下方任意节点为终点的最长路径。通过这个方法可以求一个节点左右的最长路径和,然后和这个节点值相加,就是以这个节点作为顶点的最大路径。遍历树中所有节点,就可以找到最大的路径和。

public int maxPath = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        int left = helper(cur.left);
        int right = helper(cur.right);
        maxPath = Math.max(maxPath, left + cur.val + right);
        if (cur.left != null) {
            q.offer(cur.left);
        }
        if (cur.right != null) {
            q.offer(cur.right);
        }
    }

    return maxPath;
}

public int helper(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = helper(root.left);
    int right = helper(root.right);

    int curMax = Math.max(left, right) + root.val;
    return curMax > 0 ? curMax : 0;
}

这个方法,可以通过,但是会超时。原因是每层都遍历一次,那么树下方的节点要重复调用helper很多次。
优化:helper中已经得到了一个节点左右单向最大路径和,那么就可以在helper中直接求出以当前节点为顶点的最大路径和。即把maxPath更新的那行代码移到helper中,这样每个节点只会被遍历一次。

public int maxPath = Integer.MIN_VALUE;

public int maxPathSum1(TreeNode root) {
    if (root == null) {
        return 0;
    }

    helper(root);

    return maxPath;
}

public int helper1(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = helper(root.left);
    int right = helper(root.right);
    maxPath = Math.max(maxPath, root.val + left + right);
    int curMax = Math.max(left, right) + root.val;
    return curMax > 0 ? curMax : 0;
}
点赞