226. Invert tree

226_solution1_recursion.c

#include "tree_node.h"

struct TreeNode *invertTree(struct TreeNode *root) {
  if (!root)
    return NULL;

  struct TreeNode *tmp = root->left;
  root->left = root->right;
  root->right = tmp;

  invertTree(root->left);
  invertTree(root->right);

  return root;
}

226_solution2_iterative_bfs.c

#include "tree_node.h"
#include <stdlib.h>

#define MAX_NODES 100 // constraint: number of nodes is in [0, 100]

struct TreeNode *invertTree(struct TreeNode *root) {
  if (!root)
    return NULL;

  struct TreeNode *queue[MAX_NODES];
  int head = 0, tail = 0;
  queue[tail++] = root;

  while (head < tail) {
    struct TreeNode *cur = queue[head++];

    struct TreeNode *tmp = cur->left;
    cur->left = cur->right;
    cur->right = tmp;

    if (cur->left)
      queue[tail++] = cur->left;
    if (cur->right)
      queue[tail++] = cur->right;
  }

  return root;
}

226_solution3_iterative_dfs.c

#include "tree_node.h"
#include <stdlib.h>

#define MAX_NODES 100 // constraint: number of nodes is in [0, 100]

struct TreeNode *invertTree(struct TreeNode *root) {
  struct TreeNode *stack[MAX_NODES];
  int top = 0;
  if (root)
    stack[top++] = root;

  while (top > 0) {
    struct TreeNode *cur = stack[--top];

    struct TreeNode *tmp = cur->left;
    cur->left = cur->right;
    cur->right = tmp;

    if (cur->left)
      stack[top++] = cur->left;
    if (cur->right)
      stack[top++] = cur->right;
  }

  return root;
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

226_solution1_recursion.cpp

#include "tree_node.h"

class Solution {
public:
  TreeNode *invertTree(TreeNode *root) {
    if (!root)
      return nullptr;

    TreeNode *tmp = root->left;
    root->left = root->right;
    root->right = tmp;

    invertTree(root->left);
    invertTree(root->right);

    return root;
  }
};

226_solution2_iterative_bfs.cpp

#include "tree_node.h"
#include <queue>

using namespace std;

class Solution {
public:
  TreeNode *invertTree(TreeNode *root) {
    if (!root)
      return nullptr;

    queue<TreeNode *> q;
    q.push(root);

    while (!q.empty()) {
      TreeNode *cur = q.front();
      q.pop();

      TreeNode *tmp = cur->left;
      cur->left = cur->right;
      cur->right = tmp;

      if (cur->left)
        q.push(cur->left);

      if (cur->right)
        q.push(cur->right);
    }

    return root;
  }
};

226_solution3_iterative_dfs.cpp

#include "tree_node.h"
#include <stack>
#include <utility>

using namespace std;

class Solution {
public:
  TreeNode *invertTree(TreeNode *root) {
    stack<TreeNode *> st;
    if (root)
      st.push(root);

    while (!st.empty()) {
      TreeNode *cur = st.top();
      st.pop();

      swap(cur->left, cur->right);

      if (cur->left)
        st.push(cur->left);
      if (cur->right)
        st.push(cur->right);
    }

    return root;
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

226_solution1_recursion.go

package trees

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    root.Left, root.Right = root.Right, root.Left

    invertTree(root.Left)
    invertTree(root.Right)

    return root
}

226_solution2_iterative_bfs.go

package trees

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    queue := []*TreeNode{root}

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]

        cur.Left, cur.Right = cur.Right, cur.Left

        if cur.Left != nil {
            queue = append(queue, cur.Left)
        }
        if cur.Right != nil {
            queue = append(queue, cur.Right)
        }
    }

    return root
}

226_solution3_iterative_dfs.go

package trees

func invertTree(root *TreeNode) *TreeNode {
    stack := []*TreeNode{}
    if root != nil {
        stack = append(stack, root)
    }

    for len(stack) > 0 {
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        cur.Left, cur.Right = cur.Right, cur.Left

        if cur.Left != nil {
            stack = append(stack, cur.Left)
        }
        if cur.Right != nil {
            stack = append(stack, cur.Right)
        }
    }

    return root
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

226_solution1_recursion.java

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

226_solution2_iterative_bfs.java

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;

        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);

        while (!q.isEmpty()) {
            TreeNode cur = q.poll();

            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right = tmp;

            if (cur.left != null)
                q.add(cur.left);
            if (cur.right != null)
                q.add(cur.right);
        }

        return root;
    }
}

226_solution3_iterative_dfs.java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public TreeNode invertTree(TreeNode root) {
        Deque<TreeNode> st = new ArrayDeque<>();
        if (root != null)
            st.push(root);

        while (!st.isEmpty()) {
            TreeNode cur = st.pop();

            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right = tmp;

            if (cur.left != null)
                st.push(cur.left);
            if (cur.right != null)
                st.push(cur.right);
        }

        return root;
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

226_solution1_recursion.js

const TreeNode = require("./tree_node");

var invertTree = function (root) {
  if (!root) return null;

  [root.left, root.right] = [root.right, root.left];

  invertTree(root.left);
  invertTree(root.right);

  return root;
};

226_solution2_iterative_bfs.js

const TreeNode = require("./tree_node");

var invertTree = function (root) {
  if (!root) return null;

  // index-based queue: avoids the O(n) cost of Array.shift()
  const queue = [root];
  for (let head = 0; head < queue.length; head++) {
    const cur = queue[head];

    [cur.left, cur.right] = [cur.right, cur.left];

    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
  }

  return root;
};

226_solution3_iterative_dfs.js

const TreeNode = require("./tree_node");

var invertTree = function (root) {
  const stack = [];
  if (root) stack.push(root);

  while (stack.length > 0) {
    const cur = stack.pop();

    [cur.left, cur.right] = [cur.right, cur.left];

    if (cur.left) stack.push(cur.left);
    if (cur.right) stack.push(cur.right);
  }

  return root;
};

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

226_solution1_recursion.py

from typing import Optional

from tree_node import TreeNode


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

226_solution2_iterative_bfs.py

from collections import deque
from typing import Optional

from tree_node import TreeNode


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

        q = deque([root])

        while q:
            cur = q.popleft()

            cur.left, cur.right = cur.right, cur.left

            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

        return root

226_solution3_iterative_dfs.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        stack = [root] if root else []

        while stack:
            cur = stack.pop()

            cur.left, cur.right = cur.right, cur.left

            if cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)

        return root

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

226_solution1_recursion.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = &root {
            let mut n = node.borrow_mut();
            let left = n.left.take();
            let right = n.right.take();

            // invert each subtree, then hang them back swapped
            n.left = Self::invert_tree(right);
            n.right = Self::invert_tree(left);
        }

        root
    }
}

226_solution2_iterative_bfs.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut q = VecDeque::new();
        if let Some(r) = &root {
            q.push_back(Rc::clone(r));
        }

        while let Some(cur) = q.pop_front() {
            let mut n = cur.borrow_mut();

            let n = &mut *n;
            std::mem::swap(&mut n.left, &mut n.right);

            if let Some(l) = &n.left {
                q.push_back(Rc::clone(l));
            }
            if let Some(r) = &n.right {
                q.push_back(Rc::clone(r));
            }
        }

        root
    }
}

226_solution3_iterative_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut stack = Vec::new();
        if let Some(r) = &root {
            stack.push(Rc::clone(r));
        }

        while let Some(cur) = stack.pop() {
            let mut n = cur.borrow_mut();

            let n = &mut *n;
            std::mem::swap(&mut n.left, &mut n.right);

            if let Some(l) = &n.left {
                stack.push(Rc::clone(l));
            }
            if let Some(r) = &n.right {
                stack.push(Rc::clone(r));
            }
        }

        root
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}