I solved by a different approach, in case you might find interesting... i did two dfs (one for each tree) and i stored the level and the parent of each node into a dict. on each pair (level, parent), i would check if the values add to each other (if any of the values are different, the sum would not be equal) - the only base case i had to consider is to add a buffer to differ in case 0 != empty becase in both cases, the sum of the level would be 0. here's the code, in case you're wondering: class Solution: def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: treeValues = defaultdict(int) def dfs(node, level, tree, parent): if not node: return treeValues[(level, parent)] += (node.val + 10) if tree == 1 else -(node.val + 10) dfs(node.left, level + 1, tree, node.val) dfs(node.right, level + 1, tree, node.val)
dfs(root1, 0, 1, None) dfs(root2, 0, 2, None) for i in treeValues.items(): if i[1] != 0: return False return True
what is the time complexity of this? isn't is exponential because we are calling 4 functions inside one and it calls another 4. so shouldn''t it be of the order O(4^n)?
🌲 TREE PLAYLIST: ruclips.net/video/OnSn2XEQ4MY/видео.html
Beautiful explanation! I've always had trouble dealing with tree problems but your videos really help me a lot in understanding them!
your explanations are goated bro wish you had more vids. puts every other LC solution video to shame
I solved by a different approach, in case you might find interesting... i did two dfs (one for each tree) and i stored the level and the parent of each node into a dict.
on each pair (level, parent), i would check if the values add to each other (if any of the values are different, the sum would not be equal) - the only base case i had to consider is to add a buffer to differ in case 0 != empty becase in both cases, the sum of the level would be 0.
here's the code, in case you're wondering:
class Solution:
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
treeValues = defaultdict(int)
def dfs(node, level, tree, parent):
if not node: return
treeValues[(level, parent)] += (node.val + 10) if tree == 1 else -(node.val + 10)
dfs(node.left, level + 1, tree, node.val)
dfs(node.right, level + 1, tree, node.val)
dfs(root1, 0, 1, None)
dfs(root2, 0, 2, None)
for i in treeValues.items():
if i[1] != 0: return False
return True
Hi, @Neetcode. I would suggest to include the burning of a node problem in this tress playlist
Thank you so much for clear explanation
what is the time complexity of this? isn't is exponential because we are calling 4 functions inside one and it calls another 4. so shouldn''t it be of the order O(4^n)?
7:36 Or r1 == r2 ;D
Why can't we ise BFS and check in each level if the nodes are the same in each level using like an external set for each tree?
when you are comparing those 6 nodes, you are drawing faces.
I chose a different approach to make it both long and complicated :)
neet god!
so smart