【树】二叉树的应用 I

LARRY1024 / 2024-01-25 / 原文

1. 题目
2. 应用
- 2.1. Leetcode 124. 二叉树中的最大路径和
  - 2.1.1. 题目
  - 2.1.2. 解题思路
  - 2.1.3. 代码实现

1. 题目

二叉树相关的题目：

序号	题目	难度
1	124. 二叉树中的最大路径和	困难
2

2. 应用

2.1. Leetcode 124. 二叉树中的最大路径和

2.1.1. 题目

124. 二叉树中的最大路径和

2.1.2. 解题思路

根据题意，最大路径和一定是当前节点与左右子树的对路径的贡献之和。

由于求最大路径和的时候，需要离开当前节点的时候才能得到当前节点对当前路径的贡献。因此，这里，我们需要使用后序遍历的方式求解。

我们定义一个递归函数：int dfs(TreeNode root)，用于返回当前节点对最大路径的贡献，在遍历每一个节点后，同时，更新最大路径和即可。

注意，由于节点有负值，因此，当某一个节点的贡献为负值时，需要将其去掉，即它对路径和的贡献为 $0$。

2.1.3. 代码实现

class Solution {
    private int result = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        result = Integer.MIN_VALUE;
        dfs(root);
        return result;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);
        result = Math.max(result, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}