Given a binary tree of N nodes, where every node value is a number. Find the sum of all the numbers which are formed from root to leaf paths.
Example 1:
Input :      
           6                               
         /   \                          
        3     5                      
      /   \     \
     2    5      4             
        /  \                        
       7    4  
Output: 13997
Explanation :
There are 4 leaves, hence 4 root to leaf paths:
Path                      Number
6->3->2                   632
6->3->5->7                6357
6->3->5->4                6354
6->5>4                    654   
Answer = 632 + 6357 + 6354 + 654 = 13997 
Example 2:
Input :    
           10                               
         /   \                          
        20     30                      
      /   \     
     40       60    
Output :  2630
Explanation:
Path                      Number
10->20->40                1240
10->20->60                1260
10->30                    130
1240+1260+130 = 2630
Your Task:  
You dont need to read input or print anything. Complete the function treePathsSum() which takes root node as input parameter and returns the sum of all the numbers formed by the root to leaf paths in the given Binary Tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of Tree)
Constraints:
1 ≤ N ≤ 12

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: # Your task is to complete this function

# function should return max sum level in the tree

def treePathSum(root):

    # Code here



Solutions:
def roottoleaf(root, sum1, ans):
	if root == None:
		return
	sum1 = sum1 + str(root.data)
	if root.left == None and root.right == None:
		ans.append(int(sum1))
		return
	roottoleaf(root.left, sum1, ans)
	roottoleaf(root.right, sum1, ans)

def treePathSum(root):
	sum1 = ''
	ans = []
	roottoleaf(root, sum1, ans)
	return sum(ans)


def treePathSum(root):

	def t(rt, res, ans):
		if rt is None:
			return
		if rt.left is None and rt.right is None:
			res.append(str(rt.data))
			ans.append(res.copy())
			res.pop()
			return
		res.append(str(rt.data))
		t(rt.left, res, ans)
		t(rt.right, res, ans)
		res.pop()
	r = []
	t(root, [], r)
	res = 0
	for i in r:
		if type(i) == list:
			a = ''.join(i)
			res += int(a)
	return res


def treePathSum(root, sum=0):
	rightSum = leftSum = 0
	if root.right is None and root.left is None:
		return root.data + sum * 10
	if root.right is not None:
		rightSum = treePathSum(root.right, root.data + sum * 10)
	if root.left is not None:
		leftSum = treePathSum(root.left, root.data + sum * 10)
	return leftSum + rightSum


def treePathSum(root):
	ans = 0

	def dfs(root, s):
		nonlocal ans
		if not root:
			return 0
		if not root.right and (not root.left):
			s *= 10
			s += root.data
			ans += s
			return
		s *= 10
		s += root.data
		dfs(root.left, s)
		dfs(root.right, s)
	dfs(root, 0)
	return ans


ans = 0

def pathsum(root, temp, ans):
	if root.left is None and root.right is None:
		ans.append(int(temp))
		return ans
	if root.left is not None:
		pathsum(root.left, temp + str(root.left.data), ans)
	if root.right is not None:
		pathsum(root.right, temp + str(root.right.data), ans)

def treePathSum(root):
	ans = []
	if root is not None:
		pathsum(root, str(root.data), ans)
	return sum(ans)


def treePathSum(root, data=0):
	if root == None:
		return 0
	data = data * 10 + root.data
	if root.left == None and root.right == None:
		return data
	return treePathSum(root.left, data) + treePathSum(root.right, data)


def treePathSum(root):
	global sum
	sum = 0

	def helper(root, data):
		global sum
		if root == None:
			return
		data = data * 10 + root.data
		if root.left == None and root.right == None:
			sum += data
			return
		helper(root.left, data)
		helper(root.right, data)
	helper(root, 0)
	return sum


def fun(root, l, res):
	if root == None:
		return
	l += str(root.data)
	if root.left == None and root.right == None:
		res.append(l)
	fun(root.left, l, res)
	fun(root.right, l, res)
	n = len(l) - 1
	l = l[:n]

def treePathSum(root):
	(l, res) = ('', [])
	fun(root, l, res)
	s = 0
	for i in res:
		t = int(i)
		s += t
	return s


def treePathSum(root):
	stk = []
	arr = []
	recur(root, stk, arr)
	x = 0
	for i in arr:
		x += int(i)
	return x

def recur(root, stk, arr):
	if root.left is None and root.right is None:
		s = ''
		for i in stk:
			v = i.data
			while v % 10 == 0:
				v //= 10
			s += str(v)
		s += str(root.data)
		arr.append(s)
		return
	stk.append(root)
	if root.left:
		recur(root.left, stk, arr)
	if root.right:
		recur(root.right, stk, arr)
	stk.pop()


def check(root, s, l):
	if root == None:
		return
	s = s + str(root.data)
	check(root.left, s, l)
	if root.left == None and root.right == None:
		l.append(s)
	check(root.right, s, l)
	s = s[0:-1]

def treePathSum(root):
	s = ''
	l = []
	su = 0
	check(root, s, l)
	for i in l:
		su = su + int(i)
	return su


def recur(root, ans, curr):
	if not root.left and (not root.right):
		curr.append(root.data)
		ans.append(curr.copy())
	curr.append(root.data)
	if root.left:
		recur(root.left, ans, curr.copy())
	if root.right:
		recur(root.right, ans, curr.copy())

def treePathSum(root):
	ans = []
	curr = []
	recur(root, ans, curr)
	nums = []
	for i in ans:
		num = ''
		for j in i:
			num += str(j)
		nums.append(int(num))
	total = 0
	for i in nums:
		total += i
	return total


class Runner:

	def __init__(self):
		self.ans = 0

	def run(self, root, s):
		if root is None:
			return self
		if root.left is None and root.right is None:
			self.ans += 10 * s + root.data
			return self
		s = 10 * s + root.data
		self.run(root.left, s)
		self.run(root.right, s)
		return self

	def get_ans(self):
		return self.ans

def treePathSum(root):
	return Runner().run(root, 0).get_ans()


def treePathSum(root):
	ans = 0
	list = []

	def solver(root, ans):
		if not root:
			return
		if not root.left and (not root.right):
			list.append(ans + root.data)
			return
		ans = (ans + root.data) * 10
		solver(root.left, ans)
		solver(root.right, ans)
	solver(root, 0)
	return sum(list)


def treePathSum(root):
	list = []

	def solver(root, store, list):
		if not root:
			return
		if not root.left and (not root.right):
			store += str(root.data)
			list.append(store)
			store = store[-1]
			return
		store += str(root.data)
		solver(root.left, store, list)
		solver(root.right, store, list)
	solver(root, '', list)
	ans = 0
	for i in list:
		ans += int(i)
	return ans


def treePathSum(root):
	res = []
	s = []

	def sol(root, res, s):
		if root == None:
			return
		res.append(str(root.data))
		if root.left is None and root.right is None:
			s.append(res.copy())
		sol(root.left, res, s)
		sol(root.right, res, s)
		res.pop()
	sol(root, res, s)
	s1 = 0
	for k in s:
		t1 = ''.join(k)
		s1 += int(t1)
	return s1


def solve(root, ans, res):
	if root is None:
		return
	res.append(str(root.data))
	if root.left is None and root.right is None:
		ans.append(res.copy())
	solve(root.left, ans, res)
	solve(root.right, ans, res)
	res.pop()

def treePathSum(root):
	ans = []
	res = []
	solve(root, ans, res)
	s1 = 0
	for i in ans:
		t1 = ''.join(i)
		s1 += int(t1)
	return s1


def treePathSum(root, res=0):
	if not root:
		return 0
	if not root.right and (not root.left):
		return res * 10 + root.data
	return treePathSum(root.left, res * 10 + root.data) + treePathSum(root.right, res * 10 + root.data)


def treePathSum(root):
	return treePathSum2(root, 0)

def treePathSum2(root, v):
	if root is None:
		return 0
	v = v * 10 + root.data
	if root.left is None and root.right is None:
		return v
	return treePathSum2(root.left, v) + treePathSum2(root.right, v)


def treePathSum(root):

	def cal(curr, num):
		if not curr:
			return 0
		num = num * 10 + curr.data
		if not curr.left and (not curr.right):
			return num
		a = cal(curr.left, num)
		b = cal(curr.right, num)
		return a + b
	return cal(root, 0)


def treePathSum(root):
	su = 0
	totalsum = [0]
	helper(root, su, totalsum)
	return totalsum[0]

def helper(root, su, totalsum):
	if root is None:
		return
	su = su * 10 + root.data
	if root.left is None and root.right is None:
		totalsum[0] += su
		return
	helper(root.left, su, totalsum)
	helper(root.right, su, totalsum)


def treePathSum(root):

	def dfs(node, num):
		if not node:
			return 0
		num = num * 10 + node.data
		if not node.left and (not node.right):
			return num
		return dfs(node.left, num) + dfs(node.right, num)
	return dfs(root, 0)


def treePathSum(root):

	def helper(root, s, temp):
		if root is None:
			return
		if root.left is None and root.right is None:
			l.append(temp * 10 + root.data)
			s.append(l[0])
			l.clear()
			return
		else:
			helper(root.left, s, temp * 10 + root.data)
			helper(root.right, s, temp * 10 + root.data)
	s = []
	l = []
	temp = 0
	helper(root, s, temp)
	return sum(s)


def PathProduct(root):
	if root == None:
		return []
	if root.left == None and root.right == None:
		return [root.data]
	l = PathProduct(root.left)
	r = PathProduct(root.right)
	for i in range(len(l)):
		l[i] = int(str(root.data) + str(l[i]))
	for i in range(len(r)):
		r[i] = int(str(root.data) + str(r[i]))
	return l + r

def treePathSum(root):
	return sum(PathProduct(root))


def treePathSum(root):
	path = []
	currPath = []
	Helper(root, currPath, path)
	ans = 0
	for i in path:
		strr = ''.join(i)
		ans += int(strr)
	return ans

def Helper(root, currPath, path):
	if root == None:
		return
	currPath.append(str(root.data))
	if root.left is None and root.right is None:
		path.append(currPath.copy())
	Helper(root.left, currPath, path)
	Helper(root.right, currPath, path)
	del currPath[-1]


def treePathSum(root):
	E = []
	D = [str(root.data)]
	allpath(root, D, E)
	return sum(E)

def allpath(root, D, E):
	if root.left is None and root.right is None:
		E.append(int(''.join(D.copy())))
	if root.left:
		D.append(str(root.left.data))
		allpath(root.left, D, E)
	if root.right:
		D.append(str(root.right.data))
		allpath(root.right, D, E)
	D.pop()


def helper(root, pathSum):
	if root == None:
		return 0
	pathSum = 10 * pathSum + root.data
	if root.left == None and root.right == None:
		return pathSum
	return helper(root.left, pathSum) + helper(root.right, pathSum)

def treePathSum(root):
	ans = helper(root, 0)
	return ans


def helper(root, currSum, summ):
	if root == None:
		return
	currSum[0] = 10 * currSum[0] + root.data
	if root.left == None and root.right == None:
		summ[0] += currSum[0]
	helper(root.left, currSum, summ)
	helper(root.right, currSum, summ)
	currSum[0] = currSum[0] // 10

def treePathSum(root):
	summ = [0]
	currSum = [0]
	helper(root, currSum, summ)
	return summ[0]


def function(root, s, count):
	if root == None:
		return
	s = s + str(root.data)
	function(root.left, s, count)
	if root.left == None and root.right == None:
		count.append(int(s))
	function(root.right, s, count)
	s = s[0:-1]

def treePathSum(root):
	s = ''
	count = []
	function(root, s, count)
	return sum(count)


def treePathSum(root):
	ans = []
	lis = []

	def solve(root, ans, lis):
		if root == None:
			return
		lis.append(root.data)
		if root.left == None and root.right == None:
			ans.append(lis.copy())
			ans.append('#')
		solve(root.left, ans, lis)
		solve(root.right, ans, lis)
		lis.pop(-1)
	solve(root, ans, lis)
	summ = 0
	for i in ans:
		if i != '#':
			k = ''
			for j in i:
				k += str(j)
			summ += int(k)
	return summ


def treePathSum(root):
	allSums = []
	_treePaths(root, allSums, 0)
	return sum(allSums)

def _treePaths(root, allSums, currSum):
	if root is None:
		return
	if root.left is None and root.right is None:
		currSum = currSum * 10 + root.data
		allSums.append(currSum)
	currSum = currSum * 10 + root.data
	_treePaths(root.left, allSums, currSum)
	_treePaths(root.right, allSums, currSum)


def treePathSum(root):

	def helper(cur, sum):
		if not cur:
			return 0
		sum = sum * 10 + cur.data
		if not cur.left and (not cur.right):
			return sum
		return helper(cur.left, sum) + helper(cur.right, sum)
	return helper(root, 0)


def treePathSum(root):
	if not root:
		return 0
	s = ''
	arr = []
	solve(root, arr, s)
	s1 = sum(arr)
	return s1

def solve(root, arr, s):
	if root is None:
		return arr
	s += str(root.data)
	if not root.left and (not root.right):
		p = int(s)
		arr.append(p)
	solve(root.left, arr, s)
	solve(root.right, arr, s)


def treePathSum(r):
	l = []

	def helper(root, ans):
		if root is None:
			return ans
		l.append(root.data)
		if not root.left and (not root.right):
			s = ''
			for i in l:
				s += str(i)
			ans += int(s)
		ans = helper(root.left, ans)
		ans = helper(root.right, ans)
		l.pop()
		return ans
	return helper(r, 0)


def treePathSum(root):
	return pathToLeave(root, '', 0)

def pathToLeave(root, path, level):
	if not root:
		return 0
	level += 1
	path += str(root.data)
	if not root.left and (not root.right):
		return int(path)
	left = pathToLeave(root.left, path, level)
	path = path[:level]
	right = pathToLeave(root.right, path, level)
	return left + right


def treePathSum(root):
	sum = 0
	path = []

	def pathsum(root, path):
		path.append(root.data)
		nonlocal sum
		if root.left == None and root.right == None:
			sum += int(''.join(map(str, path)))
			path.pop()
			return
		elif root.left != None:
			pathsum(root.left, path)
		if root.right != None:
			pathsum(root.right, path)
		path.pop()
	pathsum(root, [])
	return sum


def solve(root, ans, val):
	if not root:
		return 0
	val = val * 10 + root.data
	if not root.left and (not root.right):
		ans.append(val)
		return
	solve(root.left, ans, val)
	solve(root.right, ans, val)

def treePathSum(root):
	ans = []
	solve(root, ans, 0)
	return sum(ans)


def treePathSum(root):
	ans = [0]

	def dfs(root, path):
		if not root:
			return 0
		if not (root.left or root.right):
			ans[0] += 10 * path + root.data
			return
		dfs(root.left, 10 * path + root.data)
		dfs(root.right, 10 * path + root.data)
	dfs(root, 0)
	return ans[0]


def treePathSum(root):
	if root == None:
		return
	nodeStack = []
	nodeStack.append(root)
	parent = {}
	parent[root] = None
	value = 0
	while len(nodeStack) != 0:
		current = nodeStack[-1]
		nodeStack.pop(-1)
		if not current.left and (not current.right):
			value = calValue(current, parent, value)
		if current.right:
			parent[current.right] = current
			nodeStack.append(current.right)
		if current.left:
			parent[current.left] = current
			nodeStack.append(current.left)
	return value

def calValue(curr, parent, value):
	i = 0
	while curr:
		value += curr.data * pow(10, i)
		i += 1
		curr = parent[curr]
	return value


res = []

def dfs(root, s):
	if root != None:
		s = s + str(root.data)
	else:
		return 0
	if root.left == None and root.right == None:
		return int(s)
	l = r = 0
	if root.left != None:
		l = dfs(root.left, s)
	if root.right != None:
		r = dfs(root.right, s)
	return l + r

def treePathSum(root):
	return dfs(root, '')


def treePathSum(root):
	return treePathSumUtil(root, 0)

def treePathSumUtil(root, val):
	if root is None:
		return 0
	val = val * 10 + root.data
	if root.left is None and root.right is None:
		return val
	return treePathSumUtil(root.left, val) + treePathSumUtil(root.right, val)


def treePathSum(root):
	a = Paths(root)
	for i in range(len(a)):
		s = 0
		for j in range(len(a[i])):
			s += a[i][j] * 10 ** j
		a[i] = s
	return sum(a)

def Paths(root):
	ans = []
	if not root:
		return [[]]
	arr = []
	helper(root, arr, ans)
	return ans

def helper(root, arr, ans):
	if not root:
		return
	arr.append(root.data)
	if root.left is None and root.right is None:
		ans.append(arr[::-1])
		del arr[-1]
		return
	helper(root.left, arr, ans)
	helper(root.right, arr, ans)
	del arr[-1]


def treePathSumHelper(root, prev, array):
	v = prev + str(root.data)
	if not root.left and (not root.right):
		array.append(v)
	if root.left:
		treePathSumHelper(root.left, v, array)
	if root.right:
		treePathSumHelper(root.right, v, array)

def sumList(arr):
	s = 0
	for i in arr:
		s = s + int(i)
	return s

def treePathSum(root):
	results = []
	treePathSumHelper(root, '', results)
	return sumList(results)


def treePathSum(root):

	def traversal(root, arr):
		nonlocal total
		if root == None:
			return None
		arr.append(str(root.data))
		if root.left == None and root.right == None:
			total += int(''.join(arr))
		if traversal(root.left, arr) or traversal(root.right, arr):
			return True
		arr.pop()
		return False
	arr = []
	total = 0
	traversal(root, arr)
	return total


def getpaths(root, temp, result):
	if root:
		temp.append(str(root.data))
		getpaths(root.left, temp, result)
		getpaths(root.right, temp, result)
		if root.left == None and root.right == None:
			temp_ = ''.join(temp)
			result.append(temp_)
		temp.pop()

def treePathSum(root):
	temp = []
	result = []
	getpaths(root, temp, result)
	tempSum = 0
	for i in result:
		tempInt = int(i)
		tempSum += tempInt
	return tempSum


def treePathSum(root):

	def helper(root, s, res):
		if not root:
			return
		s += str(root.data)
		if root.left == None and root.right == None:
			res.append(int(s))
		helper(root.left, s, res)
		helper(root.right, s, res)
	res = []
	s = ''
	helper(root, s, res)
	return sum(res)


def treePathSum(root):

	def preorder(node, bnumber):
		if not node:
			return 0
		if not node.left and (not node.right):
			return int(str(bnumber) + str(node.data))
		else:
			return preorder(node.left, str(bnumber) + str(node.data)) + preorder(node.right, str(bnumber) + str(node.data))
	return preorder(root, '')


def treePathSum(root):

	def get_sum(root, stack, c):
		if not root:
			return
		if not root.left and (not root.right):
			stack.append(int(c + str(root.data)))
			return
		else:
			get_sum(root.left, stack, c + str(root.data))
			get_sum(root.right, stack, c + str(root.data))
	ans = []
	get_sum(root, ans, '')
	return sum(ans)


def treePathSum(root):
	x = []

	def helper(root):
		if not root:
			return None
		if root.left == None and root.right == None:
			x.append(root)
		l = helper(root.left)
		r = helper(root.right)
		return (l, r)
	helper(root)
	y = []

	def path(root, t):
		if root == None:
			return False
		if root == t:
			return True
		l = path(root.left, t)
		r = path(root.right, t)
		if l or r:
			y.append(str(root.data))
			return True
		return False
	ans = 0
	for i in x:
		path(root, i)
		y = y[::-1]
		y.append(str(i.data))
		a = int(''.join(y))
		ans += a
		y = []
	return ans


def treePathSum(root):

	def pathsum(tillnow, root):
		if root is None:
			return 0
		tillnow = tillnow * 10 + root.data
		if root.left == None and root.right == None:
			return tillnow
		return pathsum(tillnow, root.left) + pathsum(tillnow, root.right)
	return pathsum(0, root)


def treePathSum(root):
	global a
	a = []

	def sol(root, s):
		global a
		if root:
			if root.left == None and root.right == None:
				a.append(int(s + str(root.data)))
			sol(root.left, s + str(root.data))
			sol(root.right, s + str(root.data))
		return a
	k = sol(root, '')
	return sum(k)


def treePathSum(root):
	path_numbers = []

	def dfs(node, number):
		if not node:
			return
		if not (node.left or node.right):
			path_numbers.append(number + str(node.data))
			return
		dfs(node.left, number + str(node.data))
		dfs(node.right, number + str(node.data))
	dfs(root, '')
	return sum(list(map(int, path_numbers)))


def treePathSum(root):

	def dfs(curr, total):
		if curr == None:
			return 0
		total = total * 10 + curr.data
		if curr.left == None and curr.right == None:
			return total
		return dfs(curr.left, total) + dfs(curr.right, total)
	return dfs(root, 0)


def findPath(root):
	if root is None:
		return []
	l = findPath(root.left)
	r = findPath(root.right)
	X = []
	if len(l) == 0 and len(r) == 0:
		X = [str(root.data)]
	else:
		for i in l:
			X.append(str(root.data) + i)
		for i in r:
			X.append(str(root.data) + i)
	return X

def treePathSum(root):
	x = findPath(root)
	sumval = 0
	for i in x:
		sumval += int(i)
	return sumval


def treePathSum(root):
	res = 0

	def helper(root, s):
		nonlocal res
		if root == None:
			return
		s = s * 10 + root.data
		if root.left == None and root.right == None:
			res += s
			return
		helper(root.left, s)
		helper(root.right, s)
	helper(root, 0)
	return res


def treePathSum(root):
	s = [0]

	def rec(root, num):
		if not root:
			return
		num += str(root.data)
		if not root.left and (not root.right):
			s[0] += int(num)
			return
		rec(root.left, num)
		rec(root.right, num)
	rec(root, '')
	return s[0]


def treePathSum(root):
	total = 0

	def traversal(root, strg):
		nonlocal total
		if root == None:
			return
		if root.left == None and root.right == None:
			strg += str(root.data)
			total += int(strg)
			return
		strg += str(root.data)
		traversal(root.left, strg)
		traversal(root.right, strg)
	traversal(root, '')
	return total


class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def treePathSum(root):
	l = []
	path = []
	sumi = 0
	preorder(root, path, l)
	for x in l:
		count = summation(x)
		sumi += count
	return sumi

def preorder(root, path, l):
	if root:
		path.append(root.data)
		if root.left == None and root.right == None:
			l.append(path.copy())
		preorder(root.left, path, l)
		preorder(root.right, path, l)
		path.pop()

def summation(lst):
	s = ''
	for x in lst:
		s += str(x)
	s = int(s)
	return s


def treePathSum(root):

	def findpath(root, allpaths, currPath):
		if root == None:
			return
		currPath.append(str(root.data))
		if root.left == None and root.right == None:
			allpaths.append(currPath.copy())
		findpath(root.left, allpaths, currPath)
		findpath(root.right, allpaths, currPath)
		del currPath[-1]

	def findsum(root, total):
		allpaths = []
		findpath(root, allpaths, [])
		for num in allpaths:
			s = ''.join(num)
			total += int(s)
		return total
	total = 0
	return findsum(root, total)


def treePathSum(root):

	def pathSum(root, cur):
		if root == None:
			return
		if root.left == None and root.right == None:
			sum[0] = sum[0] + cur + root.data
			return
		if root:
			cur = cur + root.data
			cur = cur * 10
			pathSum(root.left, cur)
			pathSum(root.right, cur)
			cur = cur // 10
			cur = cur - root.data
	sum = [0]
	pathSum(root, 0)
	return sum[0]


def treePathSum(root):

	def dfs(cur, num):
		if cur is None:
			return 0
		num = num * 10 + cur.data
		if not cur.left and (not cur.right):
			return num
		return dfs(cur.left, num) + dfs(cur.right, num)
	return dfs(root, 0)


def treePathSum(root):
	num = 0
	return Sum(root, num)

def Sum(root, num):
	if root is None:
		return 0
	num = num * 10 + root.data
	if root.left is None and root.right is None:
		return num
	return Sum(root.left, num) + Sum(root.right, num)


def treePathSum(root):

	def f(root, s):
		if root == None:
			return
		if root.left == None and root.right == None:
			s += str(root.data)
			l[0] += int(s)
			return
		f(root.left, s + str(root.data))
		f(root.right, s + str(root.data))
	l = [0]
	f(root, '')
	return l[0]


def treePathSum(root):

	def dfs(node, items, res):
		if not node.left and (not node.right):
			res.append(int(''.join(items)))
			return
		if node.left:
			items.append(str(node.left.data))
			dfs(node.left, items, res)
			items.pop()
		if node.right:
			items.append(str(node.right.data))
			dfs(node.right, items, res)
			items.pop()
	res = []
	dfs(root, [str(root.data)], res)
	return sum(res)


def treePathSum(root):
	ans = 0

	def search(root, val):
		nonlocal ans
		if not root:
			return []
		val = val * 10 + root.data
		if root.left is None and root.right is None:
			ans += val
		search(root.left, val)
		search(root.right, val)
		return ans
	return search(root, 0)


def treePathSum(root):
	(ans, f) = ([], 0)
	x = []

	def ino(root, ans):
		nonlocal f
		if root is None:
			return
		if root.left == None and root.right == None:
			ans.append(x + [str(root.data)])
			return
		if f == 0:
			x.append(str(root.data))
		ino(root.left, ans)
		ino(root.right, ans)
		if f != 1:
			x.pop()
	ino(root, ans)
	total = 0
	for i in ans:
		total += int(''.join(i))
	return total


from collections import deque

def treePathSum(root):
	if root is None:
		return 0
	q = deque()
	ans = []
	q.append(root)
	while len(q) != 0:
		r = q.popleft()
		if r.left == None and r.right is None:
			ans.append(r.data)
		if r.left is not None:
			r.left.data += r.data * 10
			q.append(r.left)
		if r.right is not None:
			r.right.data += 10 * r.data
			q.append(r.right)
	return sum(ans)


def treePathSum(root):

	def solve(root, path):
		if not root:
			return
		if not root.left and (not root.right):
			path += str(root.data)
			ans[0] += int(path)
			return
		solve(root.left, path + str(root.data))
		solve(root.right, path + str(root.data))
	ans = [0]
	solve(root, '')
	return ans[0]


def treePathSum(root):
	globalsum = 0

	def helper(root, branchsum):
		nonlocal globalsum
		if root.left == None and root.right == None:
			globalsum += branchsum * 10 + root.data
			return
		if root.left:
			helper(root.left, branchsum * 10 + root.data)
		if root.right:
			helper(root.right, branchsum * 10 + root.data)
		return
	helper(root, 0)
	return globalsum


def treePathSum(root):

	def solve(root, string):
		nonlocal ans
		if root == None:
			return 0
		string += str(root.data)
		if root.left == None and root.right == None:
			ans += int(string)
		solve(root.left, string)
		solve(root.right, string)
	ans = 0
	string = ''
	solve(root, string)
	return ans


def treePathSum(root):

	def tree(root, val):
		if root is None:
			return 0
		val = 10 * val + root.data
		if not root.left and (not root.right):
			return val
		return tree(root.left, val) + tree(root.right, val)
	return tree(root, 0)