Given a binary tree root, return the sum of all values in the tree.
Constraints
n ≤ 100,000 where n is the number of nodes in root
Algorithm to Compute the Tree Sum using BFS
Let’s perform a Breadth First Search Algorithm to traverse the binary tree in level-by-level order. Then we can accure the sum when we visit a node. We use a queue to store the nodes of the same level and push nodes of next level into the queue.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def treeSum(self, root): if root is None: return 0 q = deque() q.append(root) ans = 0 while len(q) > 0: p = q.popleft() ans += p.val if p.left: q.append(p.left) if p.right: q.append(p.right) return ans |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def treeSum(self, root):
if root is None:
return 0
q = deque()
q.append(root)
ans = 0
while len(q) > 0:
p = q.popleft()
ans += p.val
if p.left:
q.append(p.left)
if p.right:
q.append(p.right)
return ansThe time complexity is O(N) and the space complexity is also O(N) where N is the number of the nodes in the given binary tree.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
288 wordsloading...
Last Post: Teaching Kids Programming - Algorithm to Reverse Words in a Sentence
Next Post: Teaching Kids Programming - Recursive Algorithm to Compute the Maximum Depth of the Binary Tree
