Question

Formatted question description: https://leetcode.ca/all/129.html

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.

Algorithm

Use DFS recursion to solve this problem because it is not simply adding the numbers of each node, but every time a new child node is encountered, the number of the parent node must be multiplied by 10 times and then added to next recursion.

If traversing to the leaf node, return the current accumulation result sum. If not, call the recursive function on its left and right child nodes respectively, and add the two results to return.

Code

public class Sum_Root_to_Leaf_Numbers {

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */

	public class Solution_even_better {

	    int sum = 0;
	    public int sumNumbers(TreeNode root) {
	        // directly pass prev*10+val
	        if (root == null) {
	            return 0;
            }

	        find(root, 0);

	        return sum;
	    }

	    public void find(TreeNode root, int prev) {
	        if (root.left == null && root.right == null) {
                sum += prev * 10 + root.val;
            }

	        if (root.left != null) {
	            find(root.left, prev * 10 + root.val);
            }
	        if (root.right != null) {
	            find(root.right, prev * 10 + root.val);
            }
	    }
	}


	public class Solution_optimized {

	    public int sumNumbers(TreeNode root) {
	        if(root == null)
	            return 0;

	        return dfs(root, 0, 0);
	    }

	    public int dfs(TreeNode node, int num, int sum){
	        if(node == null) {
	            return sum;
	        }

	        num = num * 10 + node.val;

	        // leaf
	        if(node.left == null && node.right == null) {
	            sum += num;
	            return sum;
	        }

	        // left subtree + right subtree
	        // @note: here is the great part, sum is never being updated until reaching a leaf node
	        //          so, it can pass corner cases like [1,0], where one side of real-root is null but sum for this side is 0
	        int newSum = dfs(node.left, num, sum) + dfs(node.right, num, sum);
	        return newSum;
	    }

	}


	public class Solution {
	    int sum = 0;

	    public int sumNumbers(TreeNode root) {

	        if (root == null) {
	            return sum;
	        }

	        // @note: key is to root-to-leaft, so at least depth=2
	        // so I just arbitrarily check root node
	        if (root.left == null && root.right == null) {
	            return root.val;
	        }

	        if (root.left != null) {
	            traverse(root.left, root.val);

	        }
	        if (root.right != null) {
	            traverse(root.right, root.val);
	        }

	        return sum;
	    }

	    private void traverse(TreeNode root, int currentSum) {
	        if (root.left == null && root.right == null) {
	            sum += currentSum * 10 + root.val;
	        }

	        if (root.left != null) {
	            traverse(root.left, currentSum * 10 + root.val);

	        }
	        if (root.right != null) {
	            traverse(root.right, currentSum * 10 + root.val);
	        }
	    }
	}


}

############

/**
 * 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 dfs(root, 0);
    }

    private int dfs(TreeNode root, int s) {
        if (root == null) {
            return 0;
        }
        s = s * 10 + root.val;
        if (root.left == null && root.right == null) {
            return s;
        }
        return dfs(root.left, s) + dfs(root.right, s);
    }
}

// OJ: https://leetcode.com/problems/sum-root-to-leaf-numbers/
// Time: O(N)
// Space: O(H)
class Solution {
    int ans = 0;
    void dfs(TreeNode *root, int sum) {
        if (!root) return;
        sum = sum * 10 + root->val;
        if (!root->left && !root->right) ans += sum;
        dfs(root->left, sum);
        dfs(root->right, sum);
    }
public:
    int sumNumbers(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root, s):
            if root is None:
                return 0
            s = s * 10 + root.val
            if root.left is None and root.right is None:
                return s
            return dfs(root.left, s) + dfs(root.right, s)

        return dfs(root, 0)

############

# 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
    """
    self.sum = 0

    def dfs(root, pathsum):
      if root:
        pathsum += root.val
        left = dfs(root.left, pathsum * 10)
        right = dfs(root.right, pathsum * 10)
        if not left and not right:
          self.sum += pathsum
        return True

    dfs(root, 0)
    return self.sum

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
	var dfs func(*TreeNode, int) int
	dfs = func(root *TreeNode, s int) int {
		if root == nil {
			return 0
		}
		s = s*10 + root.Val
		if root.Left == nil && root.Right == nil {
			return s
		}
		return dfs(root.Left, s) + dfs(root.Right, s)
	}
	return dfs(root, 0)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sumNumbers(root: TreeNode | null): number {
    function dfs(root: TreeNode | null, s: number): number {
        if (!root) return 0;
        s = s * 10 + root.val;
        if (!root.left && !root.right) return s;
        return dfs(root.left, s) + dfs(root.right, s);
    }
    return dfs(root, 0);
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root) {
    function dfs(root, s) {
        if (!root) return 0;
        s = s * 10 + root.val;
        if (!root.left && !root.right) return s;
        return dfs(root.left, s) + dfs(root.right, s);
    }
    return dfs(root, 0);
};

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, mut num: i32) -> i32 {
        if node.is_none() {
            return 0;
        }
        let node = node.as_ref().unwrap().borrow();
        num = num * 10 + node.val;
        if node.left.is_none() && node.right.is_none() {
            return num;
        }
        Self::dfs(&node.left, num) + Self::dfs(&node.right, num)
    }

    pub fn sum_numbers(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::dfs(&root, 0)
    }
}

129 - Sum Root to Leaf Numbers

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions