题目描述

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

解法1 – DFS（超时）

刚遇到题目时没有什么思路，根据题目描述“本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。”，发现这很像图数据结构的DFS算法。

我们可以把树转换为无向图，这通过向TreeNode数据结构添加Parent字段就能够实现。这样，每个节点有三个临接点分别是左子树、右子树、父节点。

static class TreeNodeEx {
        TreeNodeEx parent;
        TreeNodeEx left, right;
        int val;

        TreeNodeEx(int val) {
            this.val = val;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            TreeNodeEx that = (TreeNodeEx) o;
            return val == that.val &&
                    Objects.equals(left, that.left) &&
                    Objects.equals(right, that.right);
        }

        @Override
        public int hashCode() {
            return Objects.hash(super.hashCode(), left, right, val);
        }
}

// 将原有的树转化为带有父节点的树
TreeNodeEx copyTree(TreeNode root, List<TreeNodeEx> startPoints) {
    if (root == null)
        return null;
    TreeNodeEx newRoot = new TreeNodeEx(root.val);

    newRoot.left = copyTree(root.left, startPoints);
    if (newRoot.left != null)
        newRoot.left.parent = newRoot;

    newRoot.right = copyTree(root.right, startPoints);
    if (newRoot.right != null)
        newRoot.right.parent = newRoot;

    if (newRoot.val > 0)
        startPoints.add(newRoot);
    else
        result = Math.max(result, newRoot.val);

    return newRoot;
}

我们从树中寻找val大于0的节点作为DFS的起点，从所有的起点出发遍历完这棵树，肯定能找到包含答案的路径。我们累积走过的每一个定点的值，用当前累积的值更新全局变量result，result就存放了最终的答案。

void DFS(TreeNodeEx root, int pathSum) {
    visited.add(root);
    pathSum += root.val;
    result = Math.max(result, pathSum);

    if (root.left != null && !visited.contains(root.left)) {
        DFS(root.left, pathSum);
    }

    if (root.right != null && !visited.contains(root.right)) {
        DFS(root.right, pathSum);
    }

    if (root.parent != null && !visited.contains(root.parent)) {
        DFS(root.parent, pathSum);
    }
    visited.remove(root);
}

Set<TreeNodeEx> visited;
int result = Integer.MIN_VALUE;

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

    List<TreeNodeEx> startPoints = new ArrayList<>();

    // 复制原来的树结构，并加入parent字段；与此同时过滤val>0的节点作为DFS的根节点
    copyTree(root, startPoints);
    visited = new HashSet<>();

    for (TreeNodeEx startPt : startPoints) {
        DFS(startPt, 0);
        visited.clear();
    }
    int tmp = result;
    result = Integer.MIN_VALUE;

    return tmp;
}

很遗憾，上面的方法虽然能够找到正确的答案，但是效率太低。我一时也没有找到这种方法的优化思路，先记录下来。

解法2

方法2来自于该题目的评论区。思路是：节点n向父节点汇报以下三者中的最大值；如果节点n是叶节点则仅汇报节点n自身的值。

• 节点n的值
• 节点n的值+节点n左子树汇报的值
• 节点n的值+节点n右子树汇报的值

我们以图2为例，红色字体给出的是节点向其父节点按照上述规则汇报的值。注意，图2与图1不相同。

有了上面的图，我们把图中每个顶点“臆想”成该顶点就是整颗树的根节点，而忽略掉该节点之上的其他节点。然后我们对每个“臆想”的根节点，按照以下规则计算出的最大值。

• 根节点的值
• 根节点的值+左子树汇报的值
• 根节点的值+右子树汇报的值
• 根节点的值+左子树汇报的值+右子树汇报的值

因为我们把每个节点“臆想”成根节点，我们才会有上面规则的第4条。需要注意的是，该问题的解并不一定来源于整颗树的根节点。我们想个反例，把图2的根节点5的值调整为-∞，那么解应该来源于节点8.

我们可以把上面的操作与向父节点汇报值的过程融合，并不一定要实际的存储汇报的值，然后对树再扫描一遍。

class Solution {
    int result = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        // 清空result，防止副作用
        int tmp = result;
        result = Integer.MIN_VALUE;

        return tmp;
    }

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

        // 以root为根节点的角度来看

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

        int cond1 = root.val;
        int cond2 = root.val + lVal;
        int cond3 = root.val + rVal;

        // 看到下面两行代码，我们把root臆想成整颗树的根，那么我们就应该汇总这4种情况，因为最终的解可能来自于该节点。
        int cond4 = root.val + lVal + rVal;
        result = Math.max(result, Math.max(Math.max(cond1, cond2), Math.max(cond3, cond4)));

        // 我们还需要向父节点汇报三种情况的值
        return Math.max(cond1, Math.max(cond2, cond3));
    }
}