C++實現LeetCode(129.求根到葉節點數字之和)

Posted on by

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

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)

到此這篇關於C++實現LeetCode(129.求根到葉節點數字之和)的文章就介紹到這瞭,更多相關C++實現求根到葉節點數字之和內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：