Sum Root to Leaf Numbers(Java and Python)

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

When I met this question, I intuitively come out that recursion may be a good way to solve this problem. For a recursive solution, the base case is extremely important and it is always the key point to solve a question.

Depend on my experience, for a tree question, the root==null is always a base case, another base case in this question is decided when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this situation and it also should be a base case here. Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum variable. The reason I use an array to hold the same value is because Java can only passed by value. For example, 

in a=1; void calculate(int a){ a=a+1; } System.out.println(a); // the result is still 1 , not 2 In order to track sum value of each calculation and not return the value of sum, we should use a collection or a wrapper class to hold it  

So I use an array here to hold this sum value. If you anybody has another way to solve this problem, please leave a comment for me.

	/*
	Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
	An example is the root-to-leaf path 1->2->3 which represents the number 123.
	Find the total sum of all root-to-leaf numbers.
	For example,
	1
	/ \
	2 3
	The root-to-leaf path 1->2 represents the number 12.
	The root-to-leaf path 1->3 represents the number 13.
	Return the sum = 12 + 13 = 25.
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	/*
	When I met this question, I intuitively come out that recursion may be a good way to solve this problem.
	For a recurive solution, the base case is extremly important and it is always the key point to solve a question
	Depend on my experience, for a tree quesiton, the root==null is always a base case, another base case in this question
	is decide when the node is a leaf node. Then we know that we can use root.left==null && root.right==null to represent this
	situation and it also should be a base case here.
	Once I found the base cases, we can just apply the DFS to track each path from root to leaf and update the sum
	variable.
	the reason I use a array to hold the sum value is becasue Java can only pass by value. for example
	int a=1;
	void calculate(int a){
	a=a+1;
	}
	System.out.println(a); // the result is still 1 , not 2
	So,in order to track sum value of each calculation and not return the value of sum, we should use a collection
	or a wrapper class to hold it
	So I use a arry here to hold this sum value here
	if you any boday has other way to solve this problem please leave a comments for me.
	*/
	public class Solution {
	public int sumNumbers(TreeNode root) {
	if (root==null){
	return 0;
	}
	int[] sum={0};
	int current=0;
	getSum(root,current, sum);
	return sum[0];
	}
	public void getSum(TreeNode root, int current, int[] sum){
	if (root==null){
	return;
	}
	current=current*10+root.val;
	if (root.left==null && root.right==null){
	sum[0]=sum[0]+current;
	return;
	}
	getSum(root.left, current, sum);
	getSum(root.right, current, sum);
	}
	}

view raw SumRootTOLeafNum.java hosted with ❤ by GitHub

	"""
	Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
	An example is the root-to-leaf path 1->2->3 which represents the number 123.
	Find the total sum of all root-to-leaf numbers.
	For example,
	1
	/ \
	2 3
	The root-to-leaf path 1->2 represents the number 12.
	The root-to-leaf path 1->3 represents the number 13.
	Return the sum = 12 + 13 = 25.
	"""
	# Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	class Solution:
	# @param root, a tree node
	# @return an integer
	def sumNumbers(self, root):
	if not root:
	return 0
	current=0
	sum=[0]
	self.calSum(root, current, sum)
	return sum[0]
	def calSum(self, root, current, sum):
	if not root:
	return
	current=current*10+root.val
	if not root.left and not root.right:
	sum[0]+=current
	return
	self.calSum(root.left, current, sum)
	self.calSum(root.right,current, sum)

view raw SumRootToLeafNumbers.py hosted with ❤ by GitHub