给定二叉树，找到最大路径和。

Given a binary tree, find the maximum path sum.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: hard

标签: google, real-question, igotanoffer

目标公司: Google

参考答案摘要

题目来源 IGotAnOffer 报告，Google SWE Onsite 真题。对应 LeetCode 124，Hard。 思路分析 路径可以从任意节点到任意节点（不一定经过根）。后序 DFS，每个节点计算两个值：经过该节点的最大路径和、向上返回的最大单向路径和。 解题方法 后序 DFS + 全局变量 递归函数返回经过当前节点向上延伸的最大值。在每个节点处更新全局最大值（left + node ...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。