Description:
Given a binary tree containing digits from
0-9only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path1->2->3which represents the number123.
Find the total sum of all root-to-leaf numbers.
For example,1 / \ 2 3The root-to-leaf path
1->2represents the number12.
The root-to-leaf path1->3represents the number13.
Return the sum = 12 + 13 =25.
MySolution1:
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function(root) {
var nodeQueue = [], sumQueue = [], sum = 0;
if(root != null) {
nodeQueue.push(root);
sumQueue.push(root.val);
}
while(nodeQueue.length) {
var currentNode = nodeQueue.shift(), currentVal = sumQueue.shift();
if(currentNode.left == null && currentNode.right == null) {
sum += currentVal;
} else {
if(currentNode.left != null) {
nodeQueue.push(currentNode.left);
sumQueue.push(currentVal * 10 + currentNode.left.val);
}
if(currentNode.right != null) {
nodeQueue.push(currentNode.right);
sumQueue.push(currentVal * 10 + currentNode.right.val);
}
}
}
return sum;
};
MySolution2:
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function(root) {
if(root === null) {
return 0;
}
var sum = (arguments[1] || 0) * 10 + root.val;
if(root.left === null && root.right === null) {
return sum;
}
return sumNumbers(root.left, sum) + sumNumbers(root.right, sum);
};
Runtime: 60ms
SumRoot.png
