# 0124. 二叉樹中的最大路徑和 ## 題目地址(124. 二叉樹中的最大路徑和) <https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/description/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個非空二叉樹，返回其最大路徑和。 本題中，路徑被定義為一條從樹中任意節點出發，沿父節點-子節點連接，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點。 示例 1： 輸入：[1,2,3] 1 / \ 2 3 輸出：6 示例 2： 輸入：[-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 輸出：42 ``` ``` ## 前置知識 - 遞歸 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題目的 path 讓我誤解了，然后浪費了很多時間來解這道題 我覺得 leetcode 給的 demo 太少了，不足以讓我理解 path 的概念 因此我這里自己畫了一個圖，來補充一下，幫助大家理解 path 的概念，不要像我一樣理解錯啦。 首先是官網給的兩個例子：  接著是我自己畫的一個例子：  如圖紅色的部分是最大路徑上的節點。大家可以結合上面的 demo 來繼續理解一下 path， 除非你理解了 path，否則不要往下看。 樹的題目，基本都是考察遞歸思想的。因此我們需要思考如何去定義我們的遞歸函數，在這里我定義了一個遞歸函數，它的功能是，`返回以當前節點為根節點的MaxPath` 但是有兩個條件: 1. 根節點必須選擇 2. 左右子樹只能選擇一個 為什么要有這兩個條件? 我的想法是原問題可以轉化為：以每一個節點為根節點，分別求出 MaxPath，最后計算最大值，因此第一個條件需要滿足. 對于第二個條件，由于遞歸函數子節點的返回值會被父節點使用，因此我們如果兩個孩子都選擇了就不符合 MaxPath 的定義了。實際上這道題，當遍歷到某一個節點的時候，我們需要子節點的信息，然后同時結合自身的 val 來決定要不要選取左右子樹以及選取的話要選哪一個， 因此這個過程本質上就是`后序遍歷` 基本算法就是不斷調用遞歸函數，然后在調用過程中不斷計算和更新 MaxPath，最后在主函數中將 MaxPath 返回即可。 ## 關鍵點解析 - 遞歸 - 理解題目中的 path 定義 ## 代碼 代碼支持：JavaScript，Java，Python - JavaScript ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=124 lang=javascript * * [124] Binary Tree Maximum Path Sum */</span> <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">helper</span>(<span class="hljs-params">node, payload</span>) </span>{ <span class="hljs-keyword">if</span> (node === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> l = helper(node.left, payload); <span class="hljs-keyword">const</span> r = helper(node.right, payload); payload.max = <span class="hljs-params">Math</span>.max( node.val + <span class="hljs-params">Math</span>.max(<span class="hljs-params">0</span>, l) + <span class="hljs-params">Math</span>.max(<span class="hljs-params">0</span>, r), payload.max ); <span class="hljs-keyword">return</span> node.val + <span class="hljs-params">Math</span>.max(l, r, <span class="hljs-params">0</span>); } <span class="hljs-title">/** * @param {TreeNode} root * @return {number} */</span> <span class="hljs-keyword">var</span> maxPathSum = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">root</span>) </span>{ <span class="hljs-keyword">if</span> (root === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> payload = { max: root.val, }; helper(root, payload); <span class="hljs-keyword">return</span> payload.max; }; ``` ``` - Java ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-keyword">int</span> ans; <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxPathSum</span><span class="hljs-params">(TreeNode root)</span> </span>{ ans = Integer.MIN_VALUE; helper(root); <span class="hljs-title">// recursion</span> <span class="hljs-keyword">return</span> ans; } <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">helper</span><span class="hljs-params">(TreeNode root)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> leftMax = Math.max(<span class="hljs-params">0</span>, helper(root.left)); <span class="hljs-title">// find the max sub-path sum in left sub-tree</span> <span class="hljs-keyword">int</span> rightMax = Math.max(<span class="hljs-params">0</span>, helper(root.right)); <span class="hljs-title">// find the max sub-path sum in right sub-tree</span> ans = Math.max(ans, leftMax+rightMax+root.val); <span class="hljs-title">// find the max path sum at current node</span> <span class="hljs-keyword">return</span> max(leftMax, rightMax) + root.val; <span class="hljs-title">// according to the definition of path, the return value of current node can only be that the sum of current node value plus either left or right max path sum.</span> } } ``` ``` - Python ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> ans = float(<span class="hljs-string">'-inf'</span>) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxPathSum</span><span class="hljs-params">(self, root: TreeNode)</span> -> int:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">helper</span><span class="hljs-params">(node)</span>:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> l = helper(node.left) r = helper(node.right) self.ans = max(self.ans, max(l,<span class="hljs-params">0</span>) + max(r, <span class="hljs-params">0</span>) + node.val) <span class="hljs-keyword">return</span> max(l, r, <span class="hljs-params">0</span>) + node.val helper(root) <span class="hljs-keyword">return</span> self.ans ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 相關題目 - [113.path-sum-ii](113.path-sum-ii.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。