0124. Binary Tree Maximum Path Sum ================================== 题目信息 -------- :题号: 0124. 二叉树中的最大路径和 :难度: Hard :主题: 二叉树、路径端点、后序遍历、树形动态规划 :原题: `LeetCode 0124 `_ :重点: 用路径的唯一最高节点分类候选,区分可同时接两侧的完整路径与只能向父节点延伸一侧的返回收益 题目重述 -------- 给定一棵非空二叉树,返回任意一条非空路径的最大节点值总和。路径可从任意节点开始、在任意节点结束;相邻 节点必须由一条父子边连接,同一节点不能重复经过。路径不要求经过根,也不要求端点是叶节点。 树中节点总数在 ``1..3 * 10^4`` 范围内,节点值在 ``-1000..1000`` 范围内。所有值为负时也必须选择至少 一个真实节点,不能用空路径得到 ``0``。 自建示例 -------- * 跨过根的路径:``root = [5,-2,8,4,-6,-3,10]``,返回 ``25``,路径为 ``4 -> -2 -> 5 -> 8 -> 10``; * 最优路径位于子树:``root = [-10,9,20,null,null,15,7]``,返回 ``42``,路径 ``15 -> 20 -> 7`` 不经过整棵树根; * 全负树:``root = [-8,-3,-11]``,返回 ``-3``; * 单节点:``root = [6]``,返回 ``6``。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: int bestDownwardChain(TreeNode* node) { if (!node) { return 0; } const int leftGain = bestDownwardChain(node->left); const int rightGain = bestDownwardChain(node->right); return node->val + std::max({0, leftGain, rightGain}); } void enumerateHighestNodes(TreeNode* node, int& maximumPath) { if (!node) { return; } const int leftGain = std::max(0, bestDownwardChain(node->left)); const int rightGain = std::max(0, bestDownwardChain(node->right)); maximumPath = std::max(maximumPath, node->val + leftGain + rightGain); enumerateHighestNodes(node->left, maximumPath); enumerateHighestNodes(node->right, maximumPath); } int postorderGain(TreeNode* node, int& maximumPath) { if (!node) { return 0; } const int leftGain = std::max(0, postorderGain(node->left, maximumPath)); const int rightGain = std::max(0, postorderGain(node->right, maximumPath)); maximumPath = std::max(maximumPath, node->val + leftGain + rightGain); return node->val + std::max(leftGain, rightGain); } public: int maxPathSum(TreeNode* root) { int maximumPath = INT_MIN; postorderGain(root, maximumPath); return maximumPath; } }; 题解 ---- 端点对与最高节点 ~~~~~~~~~~~~~~~~ 原始候选可以看成任选两个节点作为端点,取树中连接它们的唯一路径,再计算路径和。直接枚举端点对已经有 ``O(n²)`` 个候选,若每次还重新寻找并累加中间节点,工作会更大。 树上任意简单路径都有一个唯一的最高节点:路径中深度最小的节点,也就是两个端点的最近公共祖先;若一个 端点是另一个祖先,最高节点就是该端点。从最高节点看,路径最多由三部分组成:左子树中的一条向下链、当前 节点、右子树中的一条向下链。某一侧也可以为空。 于是无需直接枚举端点对。可以改为枚举每个节点作为路径最高点,并只询问它的左右子树各自能提供多大的向下 收益。每条路径会归入其唯一最高节点,不重不漏。 重复求向下收益 ~~~~~~~~~~~~~~ 定义 ``bestDownwardChain(node)`` 为从 ``node`` 开始、沿孩子方向选择至多一侧延伸的最大非空路径和。当前 节点必须保留,左右孩子最多选择收益较大且为正的一侧。 ``enumerateHighestNodes`` 对每个候选最高节点分别调用这个函数求左右收益,逻辑正确,却会反复扫描相同子树。 单侧树中,根计算长度 ``n`` 的向下链,下一节点又计算长度 ``n - 1``,最坏时间 ``O(n²)``。子树收益应在 首次完成时直接返回给父节点。 两种不同结果 ~~~~~~~~~~~~ 后序处理 ``node`` 时,左右孩子各返回一条能向上连接的最佳向下链。当前节点需要产生两个不同量。 以当前节点为最高点的完整候选可以同时使用两侧: .. code-block:: text complete = node.value + leftGain + rightGain 但向父节点返回的链只能选择一侧: .. code-block:: text upward = node.value + max(leftGain, rightGain) 若把左右两侧都向父节点返回,父节点再连接后会在 ``node`` 处形成三个分支,不再是一条简单路径。完整候选 负责更新全局答案,单侧收益负责参与祖先候选,这两个状态不能混用。 负收益截断 ~~~~~~~~~~ 若孩子返回的向下收益为负,把它接入当前路径只会减小总和。路径端点允许停在当前节点,所以父节点可以完全 不使用该侧,代码将孩子收益截断为 ``max(0, gain)``。 当前节点本身不能截断为空。``postorderGain`` 返回的链必须从当前真实节点开始,完整候选也至少包含当前节点。 全局 ``maximumPath`` 初始化为 ``INT_MIN``,并在每个非空节点更新;全负树因此选择值最大的单节点,而不会 错误返回空路径的 ``0``。 后序状态走读 ~~~~~~~~~~~~ 对 ``[5,-2,8,4,-6,-3,10]``: .. list-table:: :header-rows: 1 * - 节点 - 截断后左收益 - 截断后右收益 - 完整候选 - 向上返回 * - 4 - 0 - 0 - 4 - 4 * - -6 - 0 - 0 - -6 - -6 * - -2 - 4 - 0 - 2 - 2 * - -3 - 0 - 0 - -3 - -3 * - 10 - 0 - 0 - 10 - 10 * - 8 - 0 - 10 - 18 - 18 * - 5 - 2 - 18 - 25 - 23 节点 ``5`` 的完整候选同时接入两侧得到全局答案 ``25``,但只向不存在的父节点返回较大一侧形成的 ``23``。 即使最终返回值未再使用,这一区分保证同一函数在所有子树中语义一致。 主解与复杂度 ~~~~~~~~~~~~ 公开入口采用一次后序遍历。每个节点只接收左右孩子结果、更新一次完整候选并返回一次单侧收益,重复求链的 工作全部删除。任意路径在其唯一最高节点处都会被考虑,生成的候选又都由真实父子边组成。 主解时间 ``O(n)``,递归栈 ``O(h)``,单侧树最坏为 ``O(n)``;按最高节点重复求收益的基线最坏时间 ``O(n²)``。路径和范围适合 32 位整数,返回值只占常数空间。