MediumNo. 0951
Flip Equivalent Binary Trees — LeetCode 951 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Depth-First Search, Binary Tree
- Reading time
- 3 min
- Source
- leetcode.com
The problem
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees. A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Example
- Input
- root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
- Output
- true
- Explanation
- We flipped at nodes with values 1, 3, and 5.
Python solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def dfs(root1, root2):
if root1 == root2 or (root1 is None and root2 is None):
return True
if root1 is None or root2 is None or root1.val != root2.val:
return False
return (dfs(root1.left, root2.left) and dfs(root1.right, root2.right)) or (
dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
)
return dfs(root1, root2)Complexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 951. Flip Equivalent Binary Trees is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0098 | Validate Binary Search Tree | Medium |
| 0099 | Recover Binary Search Tree | Medium |
| 0100 | Same Tree | Easy |
| 0101 | Symmetric Tree | Easy |
| 0104 | Maximum Depth of Binary Tree | Easy |
| 0110 | Balanced Binary Tree | Easy |
Frequently asked questions
- How hard is LeetCode 951. Flip Equivalent Binary Trees?
LeetCode 951. Flip Equivalent Binary Trees is rated Medium on LeetCode.
- What is the time complexity of LeetCode 951. Flip Equivalent Binary Trees?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 951. Flip Equivalent Binary Trees?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 951. Flip Equivalent Binary Trees cover?
LeetCode 951. Flip Equivalent Binary Trees is tagged Tree, Depth-First Search and Binary Tree on LeetCode.