<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>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0129. 求根到葉子節點數字之和 ## 題目地址(129. 求根到葉子節點數字之和) <https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹,它的每個結點都存放一個 0-9 的數字,每條從根到葉子節點的路徑都代表一個數字。 例如,從根到葉子節點路徑 1->2->3 代表數字 123。 計算從根到葉子節點生成的所有數字之和。 說明: 葉子節點是指沒有子節點的節點。 示例 1: 輸入: [1,2,3] 1 / \ 2 3 輸出: 25 解釋: 從根到葉子節點路徑 1->2 代表數字 12. 從根到葉子節點路徑 1->3 代表數字 13. 因此,數字總和 = 12 + 13 = 25. 示例 2: 輸入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 輸出: 1026 解釋: 從根到葉子節點路徑 4->9->5 代表數字 495. 從根到葉子節點路徑 4->9->1 代表數字 491. 從根到葉子節點路徑 4->0 代表數字 40. 因此,數字總和 = 495 + 491 + 40 = 1026. ``` ``` ## 前置知識 - 遞歸 ## 公司 - 阿里 - 百度 - 字節 ## 思路 這是一道非常適合訓練遞歸的題目。雖然題目不難,但是要想一次寫正確,并且代碼要足夠優雅卻不是很容易。 這里我們的思路是定一個遞歸的helper函數,用來幫助我們完成遞歸操作。 遞歸函數的功能是將它的左右子樹相加,注意這里不包括這個節點本身,否則會多加, 我們其實關注的就是葉子節點的值,然后通過層層回溯到root,返回即可。 整個過程如圖所示: ![](https://img.kancloud.cn/6c/2f/6c2fafb65488cb662800495748ad4518_721x366.jpg) 那么數字具體的計算邏輯,如圖所示,相信大家通過這個不難發現規律: ![](https://img.kancloud.cn/a8/6f/a86fe206f7eeae9039ae7ca95c2180a2_816x376.jpg) ## 關鍵點解析 - 遞歸分析 ## 代碼 - 語言支持:JS,C++,Python JavaScipt Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=129 lang=javascript * * [129] Sum Root to Leaf Numbers */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">helper</span>(<span class="hljs-params">node, cur</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> next = node.val + cur * <span class="hljs-params">10</span>; <span class="hljs-keyword">if</span> (node.left === <span class="hljs-params">null</span> && node.right === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> next; <span class="hljs-keyword">const</span> l = helper(node.left, next); <span class="hljs-keyword">const</span> r = helper(node.right, next); <span class="hljs-keyword">return</span> l + r; } <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-title">/** * @param {TreeNode} root * @return {number} */</span> <span class="hljs-keyword">var</span> sumNumbers = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root</span>) </span>{ <span class="hljs-title">// tag: `tree` `dfs` `math`</span> <span class="hljs-keyword">return</span> helper(root, <span class="hljs-params">0</span>); }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">sumNumbers</span><span class="hljs-params">(TreeNode* root)</span> </span>{ <span class="hljs-keyword">return</span> helper(root, <span class="hljs-params">0</span>); } <span class="hljs-keyword">private</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">helper</span><span class="hljs-params">(<span class="hljs-keyword">const</span> TreeNode* root, <span class="hljs-keyword">int</span> val)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">auto</span> ret = root->val + val * <span class="hljs-params">10</span>; <span class="hljs-keyword">if</span> (root->left == <span class="hljs-params">nullptr</span> && root->right == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> ret; <span class="hljs-keyword">auto</span> l = helper(root->left, ret); <span class="hljs-keyword">auto</span> r = helper(root->right, ret); <span class="hljs-keyword">return</span> l + r; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># class TreeNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.left = None</span> <span class="hljs-title"># self.right = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">sumNumbers</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, cur_val)</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> next_val = cur_val * <span class="hljs-params">10</span> + node.val <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> (node.left <span class="hljs-keyword">or</span> node.right): <span class="hljs-keyword">return</span> next_val left_val = helper(node.left, next_val) right_val = helper(node.right, next_val) <span class="hljs-keyword">return</span> left_val + right_val <span class="hljs-keyword">return</span> helper(root, <span class="hljs-params">0</span>) ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## 拓展 通常來說,可以利用隊列、棧等數據結構將遞歸算法轉為遞推算法。 ### 描述 使用兩個隊列: 1. 當前和隊列:保存上一層每個結點的當前和(比如49和40) 2. 結點隊列:保存當前層所有的非空結點 每次循環按層處理結點隊列。處理步驟: 1. 從結點隊列取出一個結點 2. 從當前和隊列將上一層對應的當前和取出來 3. 若左子樹非空,則將該值乘以10加上左子樹的值,并添加到當前和隊列中 4. 若右子樹非空,則將該值乘以10加上右子樹的值,并添加到當前和隊列中 5. 若左右子樹均為空時,將該節點的當前和加到返回值中 ## 實現 - 語言支持:C++,Python C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">sumNumbers</span><span class="hljs-params">(TreeNode* root)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">auto</span> ret = <span class="hljs-params">0</span>; <span class="hljs-keyword">auto</span> runningSum = <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>{root->val}; <span class="hljs-keyword">auto</span> <span class="hljs-params">queue</span> = <span class="hljs-params">vector</span><<span class="hljs-keyword">const</span> TreeNode*>{root}; <span class="hljs-keyword">while</span> (!<span class="hljs-params">queue</span>.empty()) { <span class="hljs-keyword">auto</span> sz = <span class="hljs-params">queue</span>.size(); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = <span class="hljs-params">0</span>; i < sz; ++i) { <span class="hljs-keyword">auto</span> n = <span class="hljs-params">queue</span>.front(); <span class="hljs-params">queue</span>.erase(<span class="hljs-params">queue</span>.begin()); <span class="hljs-keyword">auto</span> tmp = runningSum.front(); runningSum.erase(runningSum.begin()); <span class="hljs-keyword">if</span> (n->left != <span class="hljs-params">nullptr</span>) { runningSum.push_back(tmp * <span class="hljs-params">10</span> + n->left->val); <span class="hljs-params">queue</span>.push_back(n->left); } <span class="hljs-keyword">if</span> (n->right != <span class="hljs-params">nullptr</span>) { runningSum.push_back(tmp * <span class="hljs-params">10</span> + n->right->val); <span class="hljs-params">queue</span>.push_back(n->right); } <span class="hljs-keyword">if</span> (n->left == <span class="hljs-params">nullptr</span> && n->right == <span class="hljs-params">nullptr</span>) { ret += tmp; } } } <span class="hljs-keyword">return</span> ret; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">sumNumbers</span><span class="hljs-params">(self, root: TreeNode)</span> -> int:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> result = <span class="hljs-params">0</span> node_queue, sum_queue = [root], [root.val] <span class="hljs-keyword">while</span> node_queue: <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> node_queue: cur_node = node_queue.pop(<span class="hljs-params">0</span>) cur_val = sum_queue.pop(<span class="hljs-params">0</span>) <span class="hljs-keyword">if</span> cur_node.left: node_queue.append(cur_node.left) sum_queue.append(cur_val * <span class="hljs-params">10</span> + cur_node.left.val) <span class="hljs-keyword">if</span> cur_node.right: node_queue.append(cur_node.right) sum_queue.append(cur_val * <span class="hljs-params">10</span> + cur_node.right.val) <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> (cur_node.left <span class="hljs-keyword">or</span> cur_node.right): result += cur_val <span class="hljs-keyword">return</span> result ``` ``` ## 相關題目 - [sum-of-root-to-leaf-binary-numbers](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/) > 這道題和本題太像了,跟一道題沒啥區別 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 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>

                              哎呀哎呀视频在线观看