Invert Binary Tree Leetcode Solution
Invert Binary Tree Leetcode Problem :
Given the root of a binary tree, invert the tree, and return its root.
Invert Binary Tree Leetcode Solution :
Constraints :
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Example 1:
- Input: root = [2,1,3]
- Output: [2,3,1]
Example 2:
- Input: root = []
- Output: []
Intuition :
In the question we have to Invert the binary tree.
So we use Post Order Traversal in which first we go in Left subtree and then in Right subtree then we return back to Parent node.
When we come back to the parent node we swap it’s Left subtree and Right subtree.
Approach :
Traverse the given tree using level order traversal from right to left and store the node values in a vector. If any node is NULL then store any number not between [-100,100] (Node values range given in the question). So I stored -1000 for NULL nodes.
Create a new node root1 and initialize it with root->val.
Use Level order traversal and create a new binary tree with root node as root1
if v[i]==-1000 then add NULL in the tree.
Finally return root1.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
// Base Case
if(root==NULL)
return NULL;
invertTree(root->left); //Call the left substree
invertTree(root->right); //Call the right substree
// Swap the nodes
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
return root; // Return the root
}
};
class Solution {
private static void invert(TreeNode root) {
if (root == null) return;
TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
}
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Queue q = new LinkedList<>();
q.add(root);
while (q.size() > 0) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode temp = q.remove();
invert(temp);
if (temp.left != null) q.add(temp.left);
if (temp.right != null) q.add(temp.right);
}
}
return root;
}
}
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: #Base Case
return root
self.invertTree(root.left) #Call the left substree
self.invertTree(root.right) #Call the right substree
# Swap the nodes
root.left, root.right = root.right, root.left
return root # Return the root
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
