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.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
DFS:
public class Solution { //Time: O(n) private int sum = 0; public int sumNumbers(TreeNode root) { if (root == null) { return sum; } getSum(root, 0); return sum; } private void getSum(TreeNode root, int cur) { cur = cur * 10 + root.val; if (root.left == null && root.right == null) { sum += cur; return; } if (root.left != null) { getSum(root.left, cur); } if (root.right != null) { getSum(root.right, cur); } } }
BFS:
public class Solution { //Time: O(n) public int sumNumbers(TreeNode root) { if (root == null) { return 0; } int sum = 0; Queue<TreeNode> queue = new LinkedList<TreeNode>(); Queue<Integer> queuesum = new LinkedList<Integer>(); queue.offer(root); queuesum.offer(root.val); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); int cursum = queuesum.poll(); if (cur.left != null) { queue.offer(cur.left); queuesum.offer(cursum * 10 + cur.left.val); } if (cur.right != null) { queue.offer(cur.right); queuesum.offer(cursum * 10 + cur.right.val); } if (cur.left == null && cur.right == null) { sum += cursum; } } return sum; } }
No comments:
Post a Comment