如何做强企业网站,怎么建立购物网站,广州个人网站建设,上海网站备案核验单状态查询路径 被定义为一条从树中任意节点出发#xff0c;沿父节点-子节点连接#xff0c;达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点。 路径和 是路径中各节点值的总和。 给定一个二叉树的根节点 root… 路径 被定义为一条从树中任意节点出发沿父节点-子节点连接达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。 路径和 是路径中各节点值的总和。 给定一个二叉树的根节点 root 返回其 最大路径和即所有路径上节点值之和的最大值。 输入root [1,2,3] 输出6 解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6 这道题作为二叉树中的困难题其实做起来也没有那么困难 考虑题目定义的路径的一般情形一条路从下向上延伸到达一个最高节点后又向下延伸将最高点节点称为拐点但是拐点左侧或者右侧可能没有这个节点我们需要考虑每个节点node作为拐点都将有一个以其拐点的最大路径之和并由下面式子得到
leftRreerightTreeroot.val 这里的leftTree/rightTree作为root的左右节点为该路径和带来的贡献分别是拐点左半侧路径和拐点右半侧路径和这道题求解过程就是考察当所有的节点作为拐点时该式的结果最后取最大值显然该式具有后续遍历dfs的特点左右中dfs()方法的参数为当前节点root,返回root作为拐点儿子的半侧路径和
基准情形为递归到null时返回0递归得到调用dfs分别求左右儿子的leftTree和rightTree得到leftTree/rightTree后以该式计算当前节点为拐点的最大路径max更新全局最大路径和max返回值是当前节点root作为拐点儿子的贡献值容易有如下
return root.valMath.max(leftTree,rightTree);
即root将与其左右半侧路径中的较大者构成对上层拐点而言的更长的半侧路径
当dfs结束后max中的值就是正确结果 注意由于树中的节点可能都是负数所以在取贡献的时候如果为负数直接取0表示该节点所在的侧路径不参与组成最大路径
源码 //维护一个全局变量int maxInteger.MIN_VALUE;public int maxPathSum(TreeNode root) {//对入参进行判断if(rootnull){return 0;}dfs(root);return max;}public int dfs(TreeNode root){//递归结束条件if(rootnull){return 0;}int leftTreeMath.max(dfs(root.left),0);int rightTreeMath.max(dfs(root.right),0);int allleftTreerightTreeroot.val;//更新最大值maxMath.max(max,all);return root.valMath.max(leftTree,rightTree);}
