LeetCode 129 Sum Root to Leaf Number

 

LeetCode 129 Sum Root to Leaf Numbers

Given a root of binary tree containing digits from 0 to 9 only. Return the total sum of all root to leaf.

The question is taken from the book “Elements of Programming Interviews in Python” page 125 https://amzn.to/3y84FHQ

We see we have here these routes to path

1. 495
2. +491
3. +40

Which in total is 1026

Now let’s see how to solve it in java

/**
 * 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 {
    
    // This is an excellent trick to save us from passing params.
    int total = 0;
    
    public int sumNumbers(TreeNode root) {
        sumNumbers(root, 0);
        return total;
    }
    
    private void sumNumbers(TreeNode root, int singlePathSum) {
        
        // Step 1: Identify *no node* if no node given to us do nothing.
        if (root == null) return;
        
        // Step 2: Identify *leaf* node add the leaf node and return total.
        if (root.left == null && root.right == null) {
            total = total + (singlePathSum * 10 + root.val);
            return;
        }
        
        // Step 3: Mid tree - calc right and left.
        sumNumbers(root.left, root.val + singlePathSum * 10);
        sumNumbers(root.right, root.val + singlePathSum * 10);
        
        return;

    } 
}

As we see we have a few steps

1. First we use a trick to hold on to total in a member variable, this helps it with the recursion.
2. Step 1 we identify the extreme case of having no real root we do nothing nothing to add here.
3. Step 2 We identify a leaf node and add it to total and multiply the so far by 10.
4. Step 3 We identify we are in middle of tree and do the recursion on right and left, we let those recursion steps update the total.

To see the full question go to page 125 on book below which I think is the best book for learning programming interviews