[LeetCode] 129. Sum Root to Leaf Numbers 求根到葉節(jié)點(diǎn)數(shù)字之和

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é)點(diǎn)數(shù)字之和的題跟之前的求 Path Sum 很類似，都是利用DFS遞歸來解，這道題由于不是單純的把各個(gè)節(jié)點(diǎn)的數(shù)字相加，而是每遇到一個(gè)新的子結(jié)點(diǎn)的數(shù)字，要把父結(jié)點(diǎn)的數(shù)字?jǐn)U大10倍之后再相加。如果遍歷到葉結(jié)點(diǎn)了，就將當(dāng)前的累加結(jié)果sum返回。如果不是，則對其左右子結(jié)點(diǎn)分別調(diào)用遞歸函數(shù)，將兩個(gè)結(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é)點(diǎn)壓入棧，然后進(jìn)行while循環(huán)，取出棧頂元素，如果是葉結(jié)點(diǎn)，那么將其值加入結(jié)果res。如果其右子結(jié)點(diǎn)存在，那么其結(jié)點(diǎn)值加上當(dāng)前結(jié)點(diǎn)值的10倍，再將右子結(jié)點(diǎn)壓入棧。同理，若左子結(jié)點(diǎn)存在，那么其結(jié)點(diǎn)值加上當(dāng)前結(jié)點(diǎn)值的10倍，再將左子結(jié)點(diǎn)壓入棧，是不是跟之前的 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;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/129

類似題目：

Path Sum

Binary Tree Maximum Path Sum

參考資料：

https://leetcode.com/problems/sum-root-to-leaf-numbers/

https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41367/Non-recursive-preorder-traverse-Java-solution

https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41452/Iterative-C%2B%2B-solution-using-stack-(similar-to-postorder-traversal)

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(129.求根到葉節(jié)點(diǎn)數(shù)字之和)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)求根到葉節(jié)點(diǎn)數(shù)字之和內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論