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

淩亂°似流年 2022-12-11 12:26 122阅读 0赞

# 题目： #

[124. 二叉树中的最大路径和][124.]  
[\[编程题\]二叉树的最大路径和][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]

# 代码： #

public class code124 { 
    
        int maxValue;
    
        public int maxPathSum(TreeNode root) { 
            maxValue = Integer.MIN_VALUE;
            maxPathDown(root);
            return maxValue;
        }
    
        /** * 返回经过 node 的单边分支最大和，即 Math.max(node, node + left, node + right) * @param node * @return */
        private int maxPathDown(TreeNode node)
        { 
            if(node == null)
            { 
                return 0;
            }
            // 递归计算左右子节点的最大贡献值
            // 只有在最大贡献值大于 0 时，才会选取对应子节点
    
            // 计算左边分支最大值，左边分支如果为负数还不如不选择
            int left = Math.max(0, maxPathDown(node.left));
            // 计算右边分支最大值，右边分支如果为负数还不如不选择
            int right = Math.max(0, maxPathDown(node.right));
    
            // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            // 更新答案
    
            // left->node->right 作为路径与已经计算过历史最大值做比较
            maxValue = Math.max(maxValue, left + right + node.val);
    
            // 返回节点的最大贡献值，交给上层进行计算
            // 返回经过 node 的单边最大分支给当前 node 的父节点计算使用
            return Math.max(left, right) + node.val;
        }
    
        public static void main(String[] args) { 
            Integer nums[] = { -10, 9, 20, null, null, 15, 7};
            TreeNode root = TreeNodeUtil.arrayToTreeNode(nums);
            TreeOperation.show(root);
    
            System.out.println("***************************************");
    
            code124 test = new code124();
            int res = test.maxPathSum(root);
            System.out.println(res);
        }
    
    }

# 参考： #

1.  [二叉树中的最大路径和][Link 2]
2.  [【二叉树中的最大路径和】递归，条理清晰][Link 3]
3.  [「手画图解」二叉树中的最大路径和（涵盖细节注意点）][Link 4]
4.  [【二叉树的最大路径和】主要理解题目意思，详细图解][Link 5]
5.  [124.递归的精髓，记录一下][124. 1]
6.  [java递归的解决思路][java]
7.  [理解路径概念+简单思路解题（附图）][Link 6]
8.  [详细通俗的思路分析，多解法][Link 7]

[124.]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
[Link 1]: https://www.nowcoder.com/questionTerminal/da785ea0f64b442488c125b441a4ba4a
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b9bd1a2a6316487aaa0fd709cbe8e943.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/41f7587d05974dbc9ec76d9029eade20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/f60fac21ad23487ab64b1d8f84a70eb7.png
[Link 2]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/
[Link 3]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/
[Link 4]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/shou-hui-tu-jie-hen-you-ya-de-yi-dao-dfsti-by-hyj8/
[Link 5]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-de-zui-da-lu-jing-he-zhu-yao-li-jie-ti-/
[124. 1]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/124di-gui-de-jing-sui-ji-lu-yi-xia-by-821218213/
[java]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/javadi-gui-de-jie-jue-si-lu-by-sdwwld/
[Link 6]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/li-jie-lu-jing-gai-nian-jian-dan-si-lu-jie-ti-fu-t/
[Link 7]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-30/