JAVA练习318- 二叉树中的最大路径和

题目概览二叉树中的路径被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点root返回其最大路径和。示例 1输入root [1,2,3]输出6解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6示例 2输入root [-10,9,20,null,null,15,7]输出42解释最优路径是 15 - 20 - 7 路径和为 15 20 7 42提示树中节点数目范围是[1, 3 * 10^4]-1000 Node.val 1000来源124. 二叉树中的最大路径和 - 力扣LeetCode解题分析方法递归如果当前最大路径经过当前节点那么就有两种情况最大路径没经过当前节点父节点最大路径和一定是左边节点最长路径和大于0时 当前节点值 右边最长路径和大于0时。最大路径经过当前节点父节点当前节点的最长路径和为 当前节点值 左右两边节点中最长的一个路径和两个节点路径和都小于0则不加。因此我们可以用一个参数 maxPath 记录最大的路径和然后递归遍历二叉树方法返回以上情况二的值并在每次调用方法时同时计算情况一的值将最大的值更新到 maxPath。时间复杂度O(n)空间复杂度O(n)/** * 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 maxPath; public int maxPathSum(TreeNode root) { maxPath root.val; maxPath(root); return maxPath; } public int maxPath(TreeNode root) { if (root null) { return 0; } int left maxPath(root.left); int right maxPath(root.right); int sum root.val; if (left 0 || right 0) { sum Math.max(left, right); } int cur root.val; if (left 0 right 0) { cur left right; } maxPath Math.max(Math.max(maxPath, sum), cur); return sum; } }