[leetcode #129] Sum Root to Leaf Numbers

Problem

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:

Input: root = [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: root = [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.

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.

Idea

leaf node에 다다랐을 때 root node부터 지금까지 거쳐온 node들의 값으로 정수를 만들어 모두 더하는 문제다. depth가 1이 오를 때마다 현재 노드가 가지고 있는 값이 10배가 된다고 생각하면 된다.

depth가 1씩 증가할 때마다 부모노드가 넘겨준 값의 10배와 현재 노드의 값을 더해 sum을 계산한다.

node가 null일 때는 0을 리턴하고, 자식노드가 없는 leaf node일 경우 현재 가지고 있는 값을 리턴한다.

위 과정을 재귀함수로 구현하고 초기값을 root node와 0으로 설정하면 답을 구할 수 있다.

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) {
        return traverseTree(root, 0);
    }

    private int traverseTree(TreeNode node, int val) {
        if (node == null)
            return 0;

        int sum = val * 10 + node.val;

        if (node.left == null && node.right == null)
            return sum;

        return traverseTree(node.left, sum) + traverseTree(node.right, sum);
    }
}

좋구만~!

Reference

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