Solved! Leetcode 129. Sum Root to Leaf Numbers

Description Sum Root to Leaf Numbers

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1

<strong>Input:</strong> root = [1,2,3]
<strong>Output:</strong> 25
<strong>Explanation:</strong>
The root-to-leaf path <code>1->2</code> represents the number <code>12</code>.
The root-to-leaf path <code>1->3</code> represents the number <code>13</code>.
Therefore, sum = 12 + 13 = <code>25</code>.

Input: root = [1,2,3]

Output: 25

Explanation:

The root-to-leaf path <code>1->2</code> represents the number <code>12</code>.

The root-to-leaf path <code>1->3</code> represents the number <code>13</code>.

Therefore, sum = 12 + 13 = <code>25</code>.

Example 2

<strong>Input:</strong> root = [4,9,0,5,1]
<strong>Output:</strong> 1026
<strong>Explanation:</strong>
The root-to-leaf path <code>4->9->5</code> represents the number 495.
The root-to-leaf path <code>4->9->1</code> represents the number 491.
The root-to-leaf path <code>4->0</code> represents the number 40.
Therefore, sum = 495 + 491 + 40 = <code>1026</code>.

Input: root = [4,9,0,5,1]

Output: 1026

Explanation:

The root-to-leaf path <code>4->9->5</code> represents the number 495.

The root-to-leaf path <code>4->9->1</code> represents the number 491.

The root-to-leaf path <code>4->0</code> represents the number 40.

Therefore, sum = 495 + 491 + 40 = <code>1026</code>.

Constraints

The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 9
The depth of the tree will not exceed 10.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        int[] sum = new int[1];
        dfs(root, 0, sum);
        return sum[0];
    }
    //preorder traversal
    private void dfs(TreeNode node, int num, int[] sum){
        if(node==null){
            return;
        }
        int n = num*10+node.val;
        if(node.left==null && node.right==null){
            sum[0]+= n;
        }
        dfs(node.left, n, sum);
        dfs(node.right, n, sum);
    }
}

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

class Solution {

public int sumNumbers(TreeNode root) {

int[] sum = new int[1];

dfs(root, 0, sum);

return sum[0];

}

//preorder traversal

private void dfs(TreeNode node, int num, int[] sum){

if(node==null){

return;

}

int n = num*10+node.val;

if(node.left==null && node.right==null){

sum[0]+= n;

}

dfs(node.left, n, sum);

dfs(node.right, n, sum);

}

Time Complexity

O(n): where n is the number of nodes in a binary tree

Space Complexity

O(1)

Rate this post

Coddicted