题解 | 二叉树的最大路径和

分析

读题：

• 题目难点在于正确理解题意

• 一棵二叉树

• 注意题目对路径的定义：开始和结束结点可以是任意的结点。

• 路径要求唯一，不能重复

• 任意给出一棵二叉树的两个结点，路径指的是：分别从这两个结点向上走，找到 最近的公共祖先 结点而形成的路径。只有这样的定义下，路径才是唯一确定的。

考虑如下路径：

下图，带X的部分路径表示不符合条件

解法一：DFS(递归)

思路步骤：

• 声明int ans = Integer.MIN_VALUE存储答案

• DFS计算每一个结点的贡献值

• 由于路径唯一，在回溯时，只需要取某个父节点的俩孩子结点中的最大者。

• 对于某个节点，它关心自己走入一个子树，能从中捞取的最大收益，先不用管具体怎么走。

• 定义dfs函数：返回当前子树能向父节点“提供”的最大路径和。即，一条从父节点延伸下来的路径，能在当前子树中获得的最大收益。分为三种情况：

  • 路径停在当前子树的根节点，在这个子树中贡献：root.val
  • 走入左子树，在这个子树中的最大贡献：root.val + dfs(root.left)
  • 走入右子树，在这个子树中的最大贡献：root.val + dfs(root.right)

• 对应了前面所讲的三种选择，最大贡献取三者最大:
  即：root.val+max(dfs(root.left),dfs(root.right))

Java参考代码：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int ans = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        // write code here

        if(root==null){
            return 0;
        }
        dfs(root);
        return ans;
    }
    //DFS函数
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        //计算左孩子贡献
        int leftMax = Math.max(dfs(root.left),0);
        //计算右孩子贡献
        int rightMax = Math.max(dfs(root.right),0);
        //更新答案
        ans = Math.max(ans,root.val+leftMax+rightMax);