LCR 051. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。
示例 1：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
方法：dfs深度 —— 来源：灵茶山艾府
求当前结点左右子树哪个和更大，大的那个加入当前节点成为新路径
若子树路径和为0，不加入路径————但需要全局维护ans记录最大路径和（可能维护）
class Solution {// 记录当前全局最大路径和private int ans = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {if (root == null) return 0;dfs(root);return ans;}public int dfs(TreeNode root) {if (root == null)return 0;// 当前路径和是否为负数，若为负 不加入路径————加入值0int left_val = Math.max(dfs(root.left), 0);int right_val = Math.max(dfs(root.right), 0);// 看看加入当前结点的路径是否更新ansans = Math.max(ans, left_val + right_val + root.val);// 选择当前子树左右两支哪支值更大return Math.max(left_val, right_val) + root.val;} }
【妙~~记一下用深度递归算】