Invert Binary Tree — LeetCode 226 Python Solution
EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
- Problem
- #226
- Pattern
- Tree Traversal
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given the root of a binary tree, invert the tree, and return its root.
Example
- Input
- root = [4,2,7,1,3,6,9]
- Output
- [4,7,2,9,6,3,1]
Python solution
Python
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
l, r = self.invertTree(root.left), self.invertTree(root.right)
root.left, root.right = r, l
return rootComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 226. Invert Binary Tree 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
On study lists
This problem is on Blind 75, NeetCode 150, Grind 75 and Top Interview 150.
Frequently asked questions
- How hard is LeetCode 226. Invert Binary Tree?
- LeetCode 226. Invert Binary Tree is rated Easy on LeetCode.
- What is the time complexity of LeetCode 226. Invert Binary Tree?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 226. Invert Binary Tree?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 226. Invert Binary Tree cover?
- LeetCode 226. Invert Binary Tree is tagged Tree, Depth-First Search, Breadth-First Search and Binary Tree on LeetCode.