226. Invert Binary Tree
Easy
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
package leetcode.easy; /**
* Definition for a binary tree node. public class TreeNode { int val; TreeNode
* left; TreeNode right; TreeNode(int x) { val = x; } }
*/
public class InvertBinaryTree {
public TreeNode invertTree1(TreeNode root) {
if (root == null) {
return null;
}
TreeNode right = invertTree1(root.right);
TreeNode left = invertTree1(root.left);
root.left = right;
root.right = left;
return root;
} public TreeNode invertTree2(TreeNode root) {
if (root == null) {
return null;
}
java.util.Queue<TreeNode> queue = new java.util.LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
return root;
} @org.junit.Test
public void test1() {
TreeNode tn11 = new TreeNode(4);
TreeNode tn21 = new TreeNode(2);
TreeNode tn22 = new TreeNode(7);
TreeNode tn31 = new TreeNode(1);
TreeNode tn32 = new TreeNode(3);
TreeNode tn33 = new TreeNode(6);
TreeNode tn34 = new TreeNode(9);
tn11.left = tn21;
tn11.right = tn22;
tn21.left = tn31;
tn21.right = tn32;
tn22.left = tn33;
tn22.right = tn34;
tn31.left = null;
tn31.right = null;
tn32.left = null;
tn32.right = null;
tn33.left = null;
tn33.right = null;
tn34.left = null;
tn34.right = null;
System.out.println(tn11);
System.out.println(invertTree1(tn11));
} @org.junit.Test
public void test2() {
TreeNode tn11 = new TreeNode(4);
TreeNode tn21 = new TreeNode(2);
TreeNode tn22 = new TreeNode(7);
TreeNode tn31 = new TreeNode(1);
TreeNode tn32 = new TreeNode(3);
TreeNode tn33 = new TreeNode(6);
TreeNode tn34 = new TreeNode(9);
tn11.left = tn21;
tn11.right = tn22;
tn21.left = tn31;
tn21.right = tn32;
tn22.left = tn33;
tn22.right = tn34;
tn31.left = null;
tn31.right = null;
tn32.left = null;
tn32.right = null;
tn33.left = null;
tn33.right = null;
tn34.left = null;
tn34.right = null;
System.out.println(tn11);
System.out.println(invertTree2(tn11));
}
}