Question
Formatted question description: https://leetcode.ca/all/129.html
129 Sum Root to Leaf Numbers
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.
@tag-tree
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
Java
-
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); } } } }
-
// 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(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