O(n) Java solution, using a carry variable to save the sum along the path


  • 0
    J
    public int sumNumbers(TreeNode root) {
        if(root == null) return 0;
        return sumNumbers(root, 0);
    }
    
    private int sumNumbers(TreeNode root, int carryOver) {
        if(root == null) return 0;
        int newCarryOver = carryOver * 10 + root.val;
        if(root.left == null && root.right == null) return newCarryOver;
        return sumNumbers(root.left, newCarryOver) + sumNumbers(root.right, newCarryOver);
    }
    

    Only the leaves will actually return value, and the value is computed by multiplying the sum by 10 every time we go a level down. And if the node is a leaf, return the sum from root to this leaf, otherwise just keep going.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.