flip_equivalent_binary_trees
1from typing import Optional 2from utils import TreeNode 3 4 5# @leet start 6class Solution: 7 def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: 8 """ 9 This question asks us to figure out if two trees are flip equivalent, 10 so if you can have any sequence of flips (swapping the left and right 11 subtree) of either tree, we return true. 12 If the trees are not flip equivalent, return false. 13 14 We can solve the problem kind of like same tree -- if both trees are 15 the same, we want to return true. If both trees are equal at this level 16 and all subsequent levels with one flip, we want to return true. 17 So at each level, we check if every level is either the same or if flipping 18 this level and either flipping or keeping each subtree the same results 19 in equivalent trees. 20 """ 21 def equal(l, r): 22 if l is None and r is None: 23 return True 24 if l is None or r is None: 25 return False 26 is_flippable = l.val == r.val \ 27 and equal(l.left, r.right) \ 28 and equal(l.right, r.left) 29 is_same = l.val == r.val \ 30 and equal(l.left, r.left) \ 31 and equal(l.right, r.right) 32 return is_flippable or is_same 33 return equal(root1, root2) 34 35 36# @leet end 37 38def test(): 39 assert(2 + 2 == 4)
class
Solution:
7class Solution: 8 def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: 9 """ 10 This question asks us to figure out if two trees are flip equivalent, 11 so if you can have any sequence of flips (swapping the left and right 12 subtree) of either tree, we return true. 13 If the trees are not flip equivalent, return false. 14 15 We can solve the problem kind of like same tree -- if both trees are 16 the same, we want to return true. If both trees are equal at this level 17 and all subsequent levels with one flip, we want to return true. 18 So at each level, we check if every level is either the same or if flipping 19 this level and either flipping or keeping each subtree the same results 20 in equivalent trees. 21 """ 22 def equal(l, r): 23 if l is None and r is None: 24 return True 25 if l is None or r is None: 26 return False 27 is_flippable = l.val == r.val \ 28 and equal(l.left, r.right) \ 29 and equal(l.right, r.left) 30 is_same = l.val == r.val \ 31 and equal(l.left, r.left) \ 32 and equal(l.right, r.right) 33 return is_flippable or is_same 34 return equal(root1, root2)
8 def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: 9 """ 10 This question asks us to figure out if two trees are flip equivalent, 11 so if you can have any sequence of flips (swapping the left and right 12 subtree) of either tree, we return true. 13 If the trees are not flip equivalent, return false. 14 15 We can solve the problem kind of like same tree -- if both trees are 16 the same, we want to return true. If both trees are equal at this level 17 and all subsequent levels with one flip, we want to return true. 18 So at each level, we check if every level is either the same or if flipping 19 this level and either flipping or keeping each subtree the same results 20 in equivalent trees. 21 """ 22 def equal(l, r): 23 if l is None and r is None: 24 return True 25 if l is None or r is None: 26 return False 27 is_flippable = l.val == r.val \ 28 and equal(l.left, r.right) \ 29 and equal(l.right, r.left) 30 is_same = l.val == r.val \ 31 and equal(l.left, r.left) \ 32 and equal(l.right, r.right) 33 return is_flippable or is_same 34 return equal(root1, root2)
This question asks us to figure out if two trees are flip equivalent, so if you can have any sequence of flips (swapping the left and right subtree) of either tree, we return true. If the trees are not flip equivalent, return false.
We can solve the problem kind of like same tree -- if both trees are the same, we want to return true. If both trees are equal at this level and all subsequent levels with one flip, we want to return true. So at each level, we check if every level is either the same or if flipping this level and either flipping or keeping each subtree the same results in equivalent trees.
def
test():