[数据结构与算法]小黑感冒了蒸了桑拿搓了澡的喜茶leetcode之旅:124. 二叉树中的最大路径和

递归+最大子段和(python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_value = -inf

        def dfs(node):
            # 递归出口
            if not node:
                return 0
            # 更新以该结点为起始位置向左右孩子更新的最大路径(如果小于零则设置为0)
            left_max_path = max(dfs(node.left),0)
            right_max_path = max(dfs(node.right),0)
            # 最长路径更新
            self.max_value = max(self.max_value,left_max_path+right_max_path+node.val)
            return max(left_max_path,right_max_path) + node.val
        dfs(root)
        return self.max_value

递归+最大子段和(java)

/**
 * 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 max_value = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return this.max_value;
    }
    public int dfs(TreeNode node){
        if(node == null){
            return 0;
        }
        int left_max = Math.max(dfs(node.left),0);
        int right_max = Math.max(dfs(node.right),0);
        if(node.val+left_max+right_max > this.max_value){
            this.max_value = node.val+left_max+right_max;
        }
        return Math.max(left_max,right_max) + node.val;
    }
}

小黑生活

周三天空中的凤凰云(前两张来自导师朋友圈)

周三的喜茶跑，跑团得到了耐克纪念品的赠送

这几天每天麦当劳早餐

和师弟师妹的北京城深度骑行

周五回家路上，看到了隧道里的光

突发奇想，来到期待的公司转转，顺便等小黑驴下班一起唠唠梦想

再一次遭遇了失败，相信小黑能够换悲痛为力量

突然感冒了，嗓子干涩，去搓澡汗蒸

再去吃一个网红牛肉面，浑身暖乎乎滴

最后再喝两杯喜茶让自己开心开心

致小黑：小黑，你那么年轻，那么清纯，那么幸福，那么帅气，这就是资本，你已经比大多数人强了，希望你能每天开开心心的，不要过度忧虑，不要沉迷不良嗜好中，累了看看书，喝杯喜茶，无论能不能进入奇安信，无论以后工资多与少，不要与其他人攀比，自己开心就好-----2022年10月15日于国贸银泰大厦