二叉树中的最大路径和

原题链接

使用的方法

递归

解题思路

• 给定一个二叉树，我们需要找到路径和最大的路径。路径可以从树中的任何节点开始和结束，但必须沿着父子节点连接的方向。
• 我们可以使用递归来解决这个问题。我们定义一个全局变量 max 来记录当前找到的最大路径和。我们从根节点开始，调用一个辅助函数 dfs 来计算以当前节点为根的子树的最大路径和。
• 在 dfs 函数中，我们首先检查当前节点是否为 null，如果是，则返回 0。然后，我们递归地计算左子树和右子树的最大路径和，并将它们与当前节点的值相加，得到以当前节点为根的路径和。
• 接下来，我们更新全局变量 max，将其与当前路径和进行比较，记录下最大的路径和。
• 最后，我们返回以当前节点为根的路径和的最大值，即当前节点的值加上左子树和右子树的最大路径和中的较大值。这样，我们可以确保我们只考虑沿着父子节点连接的路径。

代码实现

/**
 * 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 max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
    public int dfs(TreeNode root){
        if(root == null)
            return 0;
        int leftRoot = Math.max(dfs(root.left),0);
        int rightRoot = Math.max(dfs(root.right),0);

        int sum = root.val + leftRoot + rightRoot;

        max = Math.max(max,sum);

        return root.val + Math.max(leftRoot,rightRoot);
    }
}