Teaching Kids Programming: Videos on Data Structures and Algorithms
Given two binary trees root0 and root1, return whether the sequence of leaves left-to-right in both trees are the same.
Constraints
n ≤ 100,000 where n is the number of nodes in root0
m ≤ 100,000 where m is the number of nodes in root1
Compare Leaf Equivalent Trees by Using Recursive Depth First Search Algorithm
We can perform a DFS (Depth First Search) Algorithm and return the leaf nodes by the order (similar to Pre-Order). Then, we can just compare the order by two given trees to see if they have same/equivalent leaves.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def checkLeafEquivalent(self, root0, root1): def dfs(root): if root is None: return [] if root.left is None and root.right is None: return [root.val] return dfs(root.left) + dfs(root.right) return dfs(root0) == dfs(root1) |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def checkLeafEquivalent(self, root0, root1):
def dfs(root):
if root is None:
return []
if root.left is None and root.right is None:
return [root.val]
return dfs(root.left) + dfs(root.right)
return dfs(root0) == dfs(root1)Time complexity is O(N+M) where N and M are the number of the nodes in two given binary trees respectively. The space complexity is also O(N+M). The DFS is implemented using Recursion.
–EOF (The Ultimate Computing & Technology Blog) —
a WordPress rating system
Last Post: String Interleaving Algorithm
Next Post: Generate the Power SubSet using Depth First Search Algorithm
