Quetion
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
Solution 1 -- Recursion
Easy to think.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null)
return root;
TreeNode leftNode = null, rightNode = null;
if (root.left != null)
leftNode = invertTree(root.left);
if (root.right != null)
rightNode = invertTree(root.right);
root.left = rightNode;
root.right = leftNode;
return root;
}
}
Solution 2 -- Iteration
BFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null)
return root;
List<TreeNode> current = new ArrayList<TreeNode>();
List<TreeNode> next;
current.add(root);
while (current.size() > 0) {
next = new ArrayList<TreeNode>();
for (TreeNode tmpNode : current) {
// inverse tmpNode
TreeNode left = tmpNode.left;
TreeNode right = tmpNode.right;
tmpNode.right = left;
tmpNode.left = right;
if (right != null)
next.add(right);
if (left != null)
next.add(left);
}
current = next;
}
return root;
}
}