Welcome to Subscribe On Youtube
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 number123
.
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 path1->2
represents the number12
. The root-to-leaf path1->3
represents the number13
. Therefore, sum = 12 + 13 =25
.
Example 2:
Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path4->9->5
represents the number 495. The root-to-leaf path4->9->1
represents the number 491. The root-to-leaf path4->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) } }