# 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，返回即可。 整個過程如圖所示：  那么數字具體的計算邏輯，如圖所示，相信大家通過這個不難發現規律：  ## 關鍵點解析 - 遞歸分析 ## 代碼 - 語言支持：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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。