Invert Binary Tree
Invert Binary Tree [Medium]
-
Write a function that takes in a Binary Tree and inverts it. In other words, the function should swap every left node in the tree for its corresponding right node.
-
Each
BinaryTreenode has an integervalue, aleftchild node, and arightchild node. Children nodes can either beBinaryTreenodes themselves orNone/null.
**Sample Input **
true = 1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
**Sample Output **
true = 1
/ \
3 2
/ \ / \
7 6 5 4
/ \
9 8
Hints
Hint 1
Start by inverting the root node of the Binary Tree. Inverting this root node simply consists of swapping its left and right child nodes, which can be done the same way as swapping two variables.
Hint 2
Once the first swap mentioned in Hint #1 is done, you must invert the root node's left child node and its right child node. You can do so just as you did for the root node.Then, you will have to continue inverting child nodes'nodes until you reach the bottom of the tree.
Hint 3
How can you accomplish the process described in Hint #2? While recursion seems appropriate, would an iterative approach work?What would be the time and space complexity implications of both approaches?
Method 1
【O(n)time∣O(n)space】
package BT;
/**
* @author zhengstars
* @date 2023/02/11
*/
public class InvertBinaryTree {
static class BinaryTree {
public int value;
public BinaryTree left;
public BinaryTree right;
public BinaryTree(int value) {
this.value = value;
}
}
public static void invertBinaryTree(BinaryTree tree) {
if(null == tree){
return;
}
BinaryTree left = tree.left;
BinaryTree right = tree.right;
tree.left = right;
tree.right = left;
invertBinaryTree(tree.left);
invertBinaryTree(tree.right);
}
}
Enjoy Reading This Article?
Here are some more articles you might like to read next: