LeetCodeHot100---LeetCode124.二叉树中最大路径和

大家好本文是逻辑自洽的今天给大家带来LeetCodeHot100中的面试高频题LeetCode124二叉树的最大路径和我们直接开始求关注先看题目路径的定义换言之就是从一个节点到另一个节点这中间不能重复经过同一个节点且必须最少有一个节点。这道题总体思路其实并不难就是从下到上枚举出每个节点的最大路径和期间在维护一个变量去不断记录最大的值最后将最大值返回就行了。二叉树只能头节点开始从上到下遍历也没法从下往上往上遍历该如何计算每个节点的最大路径和呢其实要计算最大路径和只需要计算以当前节点为根节点的左子树最大路径和left与右子树最大路径和right再将当前节点的值加上左右子树的最大路径和就行了valueleftright。如果左右子树的最大路径和其中有小于零的maxleft/right0那么就直接将该子树的最大路径和视为0换言之就是我的最大路径不会经过这条子树。那么只有返回valueleft或者valueright它们之间最大的一个现在来看代码/** * 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 ans0; public int maxPathSum(TreeNode root) { ansroot.val; dfs(root); return ans; } public int dfs(TreeNode node){ if(nodenull){ return 0; } int leftMath.max(0,dfs(node.left)); //如果左子树的最大路径和小于0那我们直接不与它构成路径 int rightMath.max(0,dfs(node.right)); int now leftrightnode.val; //当前节点为的最大路径和 ansMath.max(now,ans); //更新ans //返回当前节点与其其中一颗子树的最大路径和以便父节点来构建。 return node.valMath.max(left,right); } }最后该节点还要作为上一节点的子节点给上一节点返回最大路径但这里要注意的是这时候不能返回就不能返回valueleftright了因为如果这样返回的话那么说明你这个节点会被经过两次。其实这里发现很多时候二叉树的遍历方式它不是一开始就确立好的。而是依据题目的需要写出逻辑后才后知后觉发现我用的是前/中/后/层序遍历。这里其实就用的是后序遍历二叉树因为只有等左子树和右子树都将最大路径和返回给我时我才能计算我的最大路径和