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.

For example, 

1
2
3
  1
 / \
2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

分析

深度优先遍历

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return sum_recursion(root, 0);
    }
    
    int sum_recursion(TreeNode *root, int sum){
        if(root == NULL) {
            return 0;
        }
        if(root->left == NULL && root->right == NULL) {
            return sum * 10 + root->val;
        }
        return sum_recursion(root->left, sum*10 + root->val) + sum_recursion(root->right, sum*10 + root->val);
    }
};

解决方案2(Python)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.sum_recursion(root, 0)
        
        
    def sum_recursion(self, root, sum):
        if not root:
            return 0
        if root.left is None and root.right is None:
            return sum*10+root.val
        return self.sum_recursion(root.left, sum*10+root.val) + self.sum_recursion(root.right, sum*10+root.val)

解决方案3（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    return dfs(root, 0)
}

func dfs(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    sum = sum * 10 + root.Val
    if root.Left == nil && root.Right == nil {
        return sum
    }
    return dfs(root.Left, sum) + dfs(root.Right, sum)
}

相关问题

题目来源