Invert Binary Tree
Understand and solve the interview question "Invert Binary Tree".
We'll cover the following...
Description
In this lesson, your task is to invert a given a binary tree, T
.
Let’s look at an example below:
main.java
TreeNode.java
class Solution {public static TreeNode invertTree(TreeNode root) {return root;}}
Invert binary tree
Solution
We can solve this problem using depth-first search (DFS).
The inverse of an empty tree is the empty tree. To invert tree T
with root
and subtrees left
and right
, we keep root the same and invert the right
and left
subtrees.
Let’s review the implementation below:
main.java
TreeNode.java
class Solution {public static TreeNode invertTree(TreeNode root) {if (root == null) {return root;}TreeNode right = invertTree(root.right);TreeNode left = invertTree(root.left);root.left = right;root.right = left;return root;}public static void main(String args[]){TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right.left = new TreeNode(6);root.right.right = new TreeNode(7);Utility.print(invertTree(root));}}
Invert binary tree
Complexity measures
Time Complexity | Space Complexity |
---|---|