Solution 1 - Recursive DFS

Recursively invert the tree by swapping left and right children at every node.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0226.1 - Invert Binary Tree - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

class TreeNode{constructor(val=0,left=null,right=null){this.val=val;this.left=left;this.right=right}}
function invertTree(root){if(!root)return null;[root.left,root.right]=[root.right,root.left];invertTree(root.left);invertTree(root.right);return root}

class TreeNode{constructor(public val=0,public left:TreeNode|null=null,public right:TreeNode|null=null){}}
function invertTree(root:TreeNode|null):TreeNode|null{if(!root)return null;[root.left,root.right]=[root.right,root.left];invertTree(root.left);invertTree(root.right);return root}

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
	return root
}

func main() {}

#[derive(Debug)]
struct TreeNode {
	val: i32,
	left: Option<Box<TreeNode>>,
	right: Option<Box<TreeNode>>,
}

fn invert(mut root: Option<Box<TreeNode>>) -> Option<Box<TreeNode>> {
	if let Some(mut node) = root {
		let left = invert(node.left.take());
		let right = invert(node.right.take());
		node.left = right;
		node.right = left;
		return Some(node);
	}
	None
}

fn main() {}

Solution 2 - Iterative BFS

Use a queue; swap children as you visit each node.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0226.2 - Invert Binary Tree - Solution 2 - Iterative BFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        q = deque([root])
        while q:
            node = q.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return root

function invertTreeBfs(root){
 if(!root) return null;
 const q=[root];
 while(q.length){
  const n=q.shift();
  [n.left,n.right]=[n.right,n.left];
  if(n.left) q.push(n.left);
  if(n.right) q.push(n.right);
 }
 return root;
}

function invertTreeBfs(root: any): any {
 if(!root) return null;
 const q:any[]=[root];
 while(q.length){
  const n=q.shift();
  [n.left,n.right]=[n.right,n.left];
  if(n.left) q.push(n.left);
  if(n.right) q.push(n.right);
 }
 return root;
}

package main

import "container/list"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func invertTreeBfs(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	q := list.New()
	q.PushBack(root)

	for q.Len() > 0 {
		front := q.Front()
		q.Remove(front)
		node := front.Value.(*TreeNode)

		node.Left, node.Right = node.Right, node.Left
		if node.Left != nil {
			q.PushBack(node.Left)
		}
		if node.Right != nil {
			q.PushBack(node.Right)
		}
	}
	return root
}

func main() {}

0226 - Invert Binary Tree

Solution 1 - Recursive DFS

Solution 2 - Iterative BFS