您好,登錄后才能下訂單哦!
C++中怎么利用LeetCode求根到葉節(jié)點數(shù)字之和,很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細講解,有這方面需求的人可以來學(xué)習(xí)下,希望你能有所收獲。
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3]
1
/ \
2 3
Output: 25
Explanation:
The root-to-leaf path
1->2
represents the number
12
.
The root-to-leaf path
1->3
represents the number
13
.
Therefore, sum = 12 + 13 =
25
.
Example 2:
Input: [4,9,0,5,1]
4
/ \
9 0
/ \
5 1
Output: 1026
Explanation:
The root-to-leaf path
4->9->5
represents the number 495.
The root-to-leaf path
4->9->1
represents the number 491.
The root-to-leaf path
4->0
represents the number 40.
Therefore, sum = 495 + 491 + 40 =
1026
.
這道求根到葉節(jié)點數(shù)字之和的題跟之前的求 Path Sum 很類似,都是利用DFS遞歸來解,這道題由于不是單純的把各個節(jié)點的數(shù)字相加,而是每遇到一個新的子結(jié)點的數(shù)字,要把父結(jié)點的數(shù)字擴大10倍之后再相加。如果遍歷到葉結(jié)點了,就將當(dāng)前的累加結(jié)果sum返回。如果不是,則對其左右子結(jié)點分別調(diào)用遞歸函數(shù),將兩個結(jié)果相加返回即可,參見代碼如下:
解法一:
class Solution { public: int sumNumbers(TreeNode* root) { return sumNumbersDFS(root, 0); } int sumNumbersDFS(TreeNode* root, int sum) { if (!root) return 0; sum = sum * 10 + root->val; if (!root->left && !root->right) return sum; return sumNumbersDFS(root->left, sum) + sumNumbersDFS(root->right, sum); } };
我們也可以采用迭代的寫法,這里用的是先序遍歷的迭代寫法,使用棧來輔助遍歷,首先將根結(jié)點壓入棧,然后進行while循環(huán),取出棧頂元素,如果是葉結(jié)點,那么將其值加入結(jié)果res。如果其右子結(jié)點存在,那么其結(jié)點值加上當(dāng)前結(jié)點值的10倍,再將右子結(jié)點壓入棧。同理,若左子結(jié)點存在,那么其結(jié)點值加上當(dāng)前結(jié)點值的10倍,再將左子結(jié)點壓入棧,是不是跟之前的 Path Sum 極其類似呢,參見代碼如下:
解法二:
class Solution { public: int sumNumbers(TreeNode* root) { if (!root) return 0; int res = 0; stack<TreeNode*> st{{root}}; while (!st.empty()) { TreeNode *t = st.top(); st.pop(); if (!t->left && !t->right) { res += t->val; } if (t->right) { t->right->val += t->val * 10; st.push(t->right); } if (t->left) { t->left->val += t->val * 10; st.push(t->left); } } return res; } };
看完上述內(nèi)容是否對您有幫助呢?如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章,請關(guān)注億速云行業(yè)資訊頻道,感謝您對億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。