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

难度: 🌕

问题描述

---

解法

/**
 * 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 min = Integer.MIN_VALUE;
    int res = min;
    public int maxPathSum(TreeNode root) {
        // 思路：
        // res 记录包含左右子树 + 根节点的最大值
        // 每次返回的值为单条路径左右子树中的最大值
        mySol(root);
        return res;
    }

    private int mySol(TreeNode root) {
        // 递归终止条件
        if(root == null) {
            return min;
        }
        // root != null
        int left = mySol(root.left);;
        int right = mySol(root.right);;
        int cur = root.val;
        if(root.val >= 0) {
            if(left > 0) {
                cur += left;
            }
            if(right > 0) {
                cur += right;
            }
        } else {
            // root.val < 0 一定保留根节点
            if(left > 0) {
                cur += left;
            } 
            if(right > 0) {
                cur += right;
            }
            cur = Math.max(cur, Math.max(left, right)); // 不保留根节点，那么只有单独的左子树 | 右子树
        }
        res = Math.max(cur, res);
        return Math.max(Math.max(left, 0), Math.max(right, 0)) + root.val; // 这说明根节点一定保留，因此在主函数中需要单独讨论
    }
}

---

输出