<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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 的概念,不要像我一樣理解錯啦。 首先是官網給的兩個例子: ![](https://img.kancloud.cn/38/c0/38c0f3002458dce42463ddbda15d6608_737x277.jpg) 接著是我自己畫的一個例子: ![](https://img.kancloud.cn/8b/82/8b828f1d1ec3bd1cb4e345a779cb4a88_642x445.jpg) 如圖紅色的部分是最大路徑上的節點。大家可以結合上面的 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看