↓Skip to main content

【LeetCode 124】二叉树中的最大路径和

·150 words·1 min
WFUing
Author
WFUing
A graduate who loves coding.
Table of Contents

  • 链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/

难点
#

这题是树状dp的典型，如何在遍历树的过程中记录一些信息，是比较难的一个点。

此外，这题有两个要记录的内容，一个是树（包括子树）的 根节点 或者 根节点和一个左/右节点 中的最大值，这个要一路记录上去，用 dp 记录。还有一个就是 根节点、左节点和右节点 与之前 dp 中的最大值，这个是最后的答案，用 ans 记录。

我在解题的时候，总会忘记把 ans 跟自己做比较，也是以后需要注意的一个点。

代码
# 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans=-100000;

    public int maxPathSum(TreeNode root) {
        Map<TreeNode, Integer> dp = new HashMap<>();
        dsm(root, dp);
        return ans;
    }

    public int dsm(TreeNode node, Map<TreeNode, Integer> dp) {
        if(node == null) return 0;
        if(dp.containsKey(node)) {
            return dp.get(node);
        }
        int left = dsm(node.left, dp);
        int right = dsm(node.right, dp);
        int maxx = Math.max(node.val, Math.max(node.val+left, node.val+right));
        dp.put(node, maxx);
        ans = Math.max(ans, Math.max(node.val + left + right, maxx));
        return maxx;
    }
}