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 Depth First Search Algorithm
Using DFS (Depth First Search) Algorithm, we traverse the binary tree with parameters depth. Once we know it is a leave node, we push the current depth into a set. Then after search, we check the size of the set. If it only has one number, it means all leaves are on the same level.
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 d = set() def dfs(root, cur): if root is None: return if root.left is None and root.right is None: d.add(cur) return dfs(root.left, cur + 1) dfs(root.right, cur + 1) dfs(root, 0) return len(d) == 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
d = set()
def dfs(root, cur):
if root is None:
return
if root.left is None and root.right is None:
d.add(cur)
return
dfs(root.left, cur + 1)
dfs(root.right, cur + 1)
dfs(root, 0)
return len(d) == 1The time complexity is O(N) and the space complexity is O(N) because of we need a set, and we are using Recursion which implicitly uses a stack.
See: Binary Tree Algorithm: Checking Leaves in the Same Level
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
365 wordsloading...
Last Post: How to Exchange the Odd and Even Bits of a 32-bit Integer?
Next Post: Greedy Algorithm to Find Maximum Number After One Swap
