Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a binary tree root, return whether all leaves are at the same level.
Constraints
n ≤ 100,000 where n is the number of nodes in root
Check Same Leaves using Breadth First Search Algorithm
Yesterday, we use the DFS (Depth First Search) Algorithm (Teaching Kids Programming – Depth First Search Algorithm to Check If Leaves are Same Level in Binary Tree) to Push all Levels of Leaves into a set.
With BFS (Breadth First Search) Algorithm, we traverse the binary tree level-by-level, push all levels of leaves into a set, and finally check if the set contains only 1 integer.
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 solve(self, root): if root is None: return True Q = deque([(root, 0)]) depths = set() while len(Q) > 0: cur, d = Q.popleft() if cur.left: Q.append((cur.left, d + 1)) if cur.right: Q.append((cur.right, d + 1)) if cur.left is None and cur.right is None: depths.add(d) return len(depths) == 1 |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def solve(self, root):
if root is None:
return True
Q = deque([(root, 0)])
depths = set()
while len(Q) > 0:
cur, d = Q.popleft()
if cur.left:
Q.append((cur.left, d + 1))
if cur.right:
Q.append((cur.right, d + 1))
if cur.left is None and cur.right is None:
depths.add(d)
return len(depths) == 1However, we can just return False without continuing traversing once we know that there are more than 1 levels.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def solve(self, root): if root is None: return True Q = deque([(root, 0)]) depths = set() while len(Q) > 0: cur, d = Q.popleft() if cur.left: Q.append((cur.left, d + 1)) if cur.right: Q.append((cur.right, d + 1)) if cur.left is None and cur.right is None: depths.add(d) if len(depths) > 1: return False return True |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def solve(self, root):
if root is None:
return True
Q = deque([(root, 0)])
depths = set()
while len(Q) > 0:
cur, d = Q.popleft()
if cur.left:
Q.append((cur.left, d + 1))
if cur.right:
Q.append((cur.right, d + 1))
if cur.left is None and cur.right is None:
depths.add(d)
if len(depths) > 1:
return False
return TrueAlternatively, we can use a variable (last depth integer) to replace the usage of a set:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def solve(self, root): if root is None: return True Q = deque([(root, 0)]) last = -1 while len(Q) > 0: cur, d = Q.popleft() if cur.left: Q.append((cur.left, d + 1)) if cur.right: Q.append((cur.right, d + 1)) if cur.left is None and cur.right is None: if last != -1 and d != last: return False last = d return True |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def solve(self, root):
if root is None:
return True
Q = deque([(root, 0)])
last = -1
while len(Q) > 0:
cur, d = Q.popleft()
if cur.left:
Q.append((cur.left, d + 1))
if cur.right:
Q.append((cur.right, d + 1))
if cur.left is None and cur.right is None:
if last != -1 and d != last:
return False
last = d
return True–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Greedy Algorithm to Find Maximum Number After One Swap
Next Post: Algorithm to Sum of Unique Elements
