Recursive version
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
Iterative version
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
Deque<TreeNode> stack = new LinkedList<>(List.of(root));
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
if (cur != null) {
stack.push(cur);
stack.push(null);
if (cur.right != null) stack.push(cur.right);
if (cur.left != null) stack.push(cur.left);
} else {
cur = stack.pop();
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
}
}
return root;
}
}
Recursive version
class Solution {
private boolean symmetricPair(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
// must be at most one null
if (left == null || right == null || left.val != right.val) return false;
return symmetricPair(left.right, right.left) && symmetricPair(left.left, right.right);
}
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return symmetricPair(root.left, root.right);
}
}
Iterative version
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> q = new LinkedList<>();
q.add(root.left);
q.add(root.right);
while (!q.isEmpty()) {
TreeNode leftNode = q.poll();
TreeNode rightNode = q.poll();
if (leftNode == null && rightNode == null) continue;
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;
// outside
q.add(leftNode.left);
q.add(rightNode.right);
// inside
q.add(leftNode.right);
q.add(rightNode.left);
}
return true;
}
}