C++中怎么利用LeetCode求根到葉節點數字之和

C++中怎么利用LeetCode求根到葉節點數字之和，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

[LeetCode] 129. Sum Root to Leaf Numbers 求根到葉節點數字之和

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

.

這道求根到葉節點數字之和的題跟之前的求 Path Sum 很類似，都是利用DFS遞歸來解，這道題由于不是單純的把各個節點的數字相加，而是每遇到一個新的子結點的數字，要把父結點的數字擴大10倍之后再相加。如果遍歷到葉結點了，就將當前的累加結果sum返回。如果不是，則對其左右子結點分別調用遞歸函數，將兩個結果相加返回即可，參見代碼如下：

解法一：

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);
    }
};

我們也可以采用迭代的寫法，這里用的是先序遍歷的迭代寫法，使用棧來輔助遍歷，首先將根結點壓入棧，然后進行while循環，取出棧頂元素，如果是葉結點，那么將其值加入結果res。如果其右子結點存在，那么其結點值加上當前結點值的10倍，再將右子結點壓入棧。同理，若左子結點存在，那么其結點值加上當前結點值的10倍，再將左子結點壓入棧，是不是跟之前的 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;
    }
};

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。