Invert Binary Tree 🧠
LeetCode Link: Invert Binary Tree
Difficulty: Easy
Problem Explanation 📝
Problem: LeetCode 226 - Invert Binary Tree
Description: Given the root of a binary tree, invert the tree and return its root.
Intuition: To invert a binary tree, we need to swap the left and right subtrees of each node. This can be done recursively, starting from the root node and swapping the children of each node.
Approach:
- Implement a recursive function to invert the binary tree.
- If the root is null, return null.
- Swap the left and right children of the root node.
- Recursively invert the left and right subtrees.
- Return the modified root.
⌛ Time Complexity: The time complexity of the approach is O(n), where n is the number of nodes in the binary tree. We visit each node once.
💾 Space Complexity: The space complexity is O(h), where h is the height of the binary tree. This is the space used by the recursive call stack.
Solutions 💡
Cpp 💻
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *invertTree(TreeNode *root) {
// Base case: if the root is null, return null
if (root == nullptr) {
return nullptr;
}
// Swap the left and right children of the root node
swap(root->left, root->right);
// Recursively invert the left and right subtrees
invertTree(root->left);
invertTree(root->right);
return root;
}
};
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: TreeNode) -> TreeNode:
if not root:
return None
# Swap left and right subtrees
root.left, root.right = root.right, root.left
# Recursively invert left and right subtrees
self.invertTree(root.left)
self.invertTree(root.right)
return root