个人网站制作方法,黄山旅游攻略必玩的景点,网站建设经验王者荣耀恺和,公司取名网免费版今天我们看一道 leetcode hard 难度题目#xff1a;二叉树中的最大路径和。 题目 二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点… 今天我们看一道 leetcode hard 难度题目二叉树中的最大路径和。 题目 二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root 返回其 最大路径和 。 示例1 输入root [1,2,3]
输出6
解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6 思考 第一想法是这道题不安常理出牌因为路径竟然不是自上而下的而是可以横向蛇形游走的如下图 尝试动态规划 第二想法是这种蛇形游走的路径求路径最大值应该用什么方法大概率是暴力解法因为 必须遍历完所有节点才知道是否有更大的值的可能性而应对暴力解法最好的策略是动态规划那么应该如何定义状态经过一番思考二叉树点到点之间仅有唯一一条路径如果我们能枚举计算经过每个点的所有可能路径的最大值那么找到其中最大的就可以得到答案。但可惜的是以 “点” 为变量没办法写转移方程。 以暴力解法为基础思考 此时要切换想法经过一些思考我决定以正序角度模拟一下寻找最大路径和的思路首先选择一个起点找到以该起点开始的最大路径合。那么从该起点就有最多 3 种走法分别是向根节点走、左子节点、右子节点走 最暴力的解法是遍历每个点把所有方向都走一遍找到所有可能的最大值。 这无疑是一个最有效的兜底解法但效率太低那么为了提升效率假设一条路径的最大潜力已经计算过一次了那么一条新路径经过时就没必要重新算一遍。所以我们要寻找每个方向的最大贡献。 寻找每个方向的最大贡献 假设我们提前找到了经过每个点的最大贡献如下 根节点的最大贡献 10 的含义为从 3 向根节点走所有可能路径能带来的最大正数收益为 10。所以此时最大路径和显然为5 3 10 18. 但此时矛盾来了根节点的最大贡献 10 是从 3 向根节点走的角度定义的它有两个致命问题 每个节点的最大贡献最好只能有一个数字依赖方向的话复杂度太高了。如果要依赖方向那么从根节点右子节点走向根节点的最大贡献其实依赖从左子结点出发的最大贡献相互死锁了。 这种最大贡献几乎不可能找到再花时间思考只是浪费时间所以我们要改变策略了。再想想二叉树的特征是什么怎么样能最稳定的定义每个节点的最大贡献很容易想到的是以树的深度来定义即 以当前节点向子节点遍历时能带来的最大贡献。这种最大贡献是比较容易计算的。 每个子树的最大贡献 如上图所示以 8 这个节点的子树假设通过一系列递归找到它能提供的最大贡献就是 8且这个贡献必须是一条没有分叉的线这样这个最大贡献对于它的父节点才有意义即父节点可以把这个节点连上形成一条更长的没有分叉的线。如果子线都有分叉整条线就会存在分叉就不符合题意了。 这个 8 很容易计算从叶子结点向上推找到最大且大于 0 的子节点连成线即可。 但回到这道题如果我们仅仅计算了每个点所在子树的最大贡献那么其最大值仅是垂直的线中的最大值没有考虑到该题路径可以横向蛇形游走的特性 如上图所示红色的数字为以该点开始的子树的最大贡献那么根节点 32 其实就是红色路径提供的路径和对于纵向走位来说是最大的但并不是本题最大的。本题最大的值还得把下图红色的路径考虑上变成一个横向的线此时最大值达到了 32 8 40 但其实要把线变成横向的也仅需要多考虑另一个子节点而已因为所有子树的最大贡献已经提前算好根本无需再深入子子节点。也就是说在计算最大路径和时重要内容字体加粗 经过该点的最大路径和要同时考虑该点 左右子树最大贡献也就是此时路径会形成类似倒扣的 U 型。但该节点的最大贡献呢只能考虑该点 左 or 右子树最大贡献的不能形成倒扣的 U 型因为这个最大贡献需要被其父节点作第 1 条规则时考虑如果此时已经是倒扣 U 型了那么父节点再分叉一次倒扣的 U 型就不是一条线了可能会形成如下图所示奇怪的形状: 这就是本题最精彩的思考点。 代码实现 想通了之后代码就很简单了 function maxPathSum(root: TreeNode | null): number {let maxValue -Infinityfunction maxOneLinePathByNode(node: TreeNode): number {// 如果节点为空返回负无穷必然不会被最大路径和带上if (node null) return -Infinity// 左子树最大贡献(如果为负数则为 0表示不带上左子树)const leftChildMaxValue Math.max(maxOneLinePathByNode(node.left), 0)// 右子树最大贡献 - 同理const rightChildMaxValue Math.max(maxOneLinePathByNode(node.right), 0)// 经过该点的最大路径和const currentPointMaxValue node.val leftChildMaxValue rightChildMaxValue// 刷新 maxValuemaxValue Math.max(maxValue, currentPointMaxValue)// 返回不分叉的子树最大贡献return node.val Math.max(leftChildMaxValue, rightChildMaxValue)}maxOneLinePathByNode(root)return maxValue
}; 因为从根节点开始递归可以算出所有子树的最大贡献把经过每一个点的路径都考虑到了所以答案是不重不漏的。 总结 该题有两个难点 找到子树最大贡献思考方向。子树最大贡献与最大路径和的计算方式稍有不同需要分别处理。 最后在从根节点递归寻找子树最大贡献时就可以顺便计算出最大路径和一定程度上是 “目标的副产物”甚至可以怀疑该题是在思考子树最大贡献时逆向推导出来的副产物。另一方面也说明了子树最大贡献的重要性它的一个衍生计算就可以是一道 hard 题。 讨论地址是精读《算法 - 二叉树中的最大路径和》· Issue #504 · dt-fe/weekly 如果你想参与讨论请 点击这里每周都有新的主题周末或周一发布。前端精读 - 帮你筛选靠谱的内容。 版权声明自由转载-非商用-非衍生-保持署名创意共享 3.0 许可证
