Обратное двоичное дерево в O (1).

    struct NormalNode {
      int value;
      struct NormalNode *left;
      struct NormalNode *right;
    };

    struct ReversedNode {
      int value;
      struct ReversedNode *right;
      struct ReversedNode *left;
    };

    struct ReversedNode *reverseTree(struct NormalNode *root) {
      return (struct ReversedNode *)root;
    }

В этом вопросе есть несколько интересных моментов. Во-первых, поскольку ваш язык Java, вы, скорее всего, будете иметь общий узел класс, что-то вроде этого:

class Node<T> {
    private final T data;
    private final Node left;
    private final Node right;
    public Node<T>(final T data, final Node left, final Node right) {
        this.data  = data;
        this.left  = left;
        this.right = right;
    }
    ....
}

Во-вторых, реверсирование, иногда называемое инвертированием, может быть выполнено либо путем мутации левого и правого полей узла, либо путем создания нового узла, точно такого же, как исходный, но с его левыми и правыми дочерними элементами."Первый подход показан в другом ответе , в то время как второй подход показан здесь:

class Node<T> {
    // See fields and constructor above...

    public Node<T> reverse() {
        Node<T> newLeftSubtree = right == null ? null : right.reverse();
        Node<T> newRightSubtree = left == null ? null : left.reverse();
        return Node<T>(data, newLeftSubtree, newRightSubtree); 
    }
}

Идея не мутировать структуру данных является одной из идей, лежащих в основе устойчивых структур данных, которые довольно интересны.

Есть много способов там для вас, и многие люди скажут сделать много новых ответов, но лучший способ решить вопросы дерева (почти) с помощью рекурсии, и с помощью этого вы можете решить любые другие проблемы, связанные с деревом.

Итак, вот решение для вас, как вы можете обратить двоичное дерево -

Для этого вам нужно будет на каждом шагу менять левого и правого ребенка родителя, поэтому используйте функцию swap для замены левого и правого ребенка и делайте этот процесс и для их детей тоже.

void reversetree(struct node* head)
{
//first check for the exception whether does it even exit or not
if(head==NULL)
return ;

reversetree(head->left);    //reverse call for left child
reversetree(head->right);   //same reverse call for right child 

//now next these steps will swap the children
struct node* temp=head->left;
head->left=head->right;
head->right=head->left;
//now exit the function and you are done :)
}

Измените обход предзаказа, чтобы перевернуть узлы перед дальнейшим обходом.

#python3
def flipTree(node):
    if node is None:
       return
    #flip nodes
    node.left,node.right = node.right,node.left
    flipTree(node.left)
    flipTree(node.right)

Вы можете рекурсивно поменять местами левый и правый узлы, как показано ниже;

// helper method
private static void reverseTree(TreeNode<Integer> root) {
    reverseTreeNode(root);
}

private static void reverseTreeNode(TreeNode<Integer> node) {
    TreeNode<Integer> temp = node.left;
    node.left   = node.right;
    node.right  = temp;

    if(node.left != null)
        reverseTreeNode(node.left);

    if(node.right != null)
        reverseTreeNode(node.right);
}

Демонстрационный код для Java

import java.util.LinkedList;
import java.util.Queue;

public class InvertBinaryTreeDemo {

    public static void main(String[] args) {

        // root node
        TreeNode<Integer> root  = new TreeNode<>(6);

        // children of root
        root.left               = new TreeNode<Integer>(3);
        root.right              = new TreeNode<Integer>(4);

        // grand left children of root
        root.left.left          = new TreeNode<Integer>(7);
        root.left.right         = new TreeNode<Integer>(3);

        // grand right childrend of root
        root.right.left         = new TreeNode<Integer>(8);
        root.right.right        = new TreeNode<Integer>(1);

        System.out.println("Before invert");
        traverseTree(root);

        reverseTree(root);

        System.out.println("\nAfter invert");
        traverseTree(root);
    }

    // helper method
    private static void reverseTree(TreeNode<Integer> root) {
        reverseTreeNode(root);
    }

    private static void reverseTreeNode(TreeNode<Integer> node) {
        TreeNode<Integer> temp = node.left;
        node.left   = node.right;
        node.right  = temp;

        if(node.left != null)
            reverseTreeNode(node.left);

        if(node.right != null)
            reverseTreeNode(node.right);
    }

    // helper method for traverse
    private static void traverseTree(TreeNode<Integer> root) {
        Queue<Integer> leftChildren     = new LinkedList<>();
        Queue<Integer> rightChildren    = new LinkedList<>();

        traverseTreeNode(root, leftChildren, rightChildren);

        System.out.println("Tree;\n*****");

        System.out.printf("%3d\n", root.value);

        int count = 0;
        int div = 0;
        while(!(leftChildren.isEmpty() && rightChildren.isEmpty())) {
            System.out.printf("%3d\t%3d\t", leftChildren.poll(), rightChildren.poll());
            count += 2;
            div++;
            if( (double)count == (Math.pow(2, div))) {
                System.out.println();
                count = 0;
            }
        }

        System.out.println();
    }

    private static void traverseTreeNode(TreeNode<Integer> node, Queue<Integer> leftChildren, Queue<Integer> rightChildren) {
        if(node.left != null)
            leftChildren.offer(node.left.value);

        if(node.right != null)
            rightChildren.offer(node.right.value);

        if(node.left != null) {
            traverseTreeNode(node.left, leftChildren, rightChildren);
        }

        if(node.right != null) {
            traverseTreeNode(node.right, leftChildren, rightChildren);
        }
    }

    private static class TreeNode<E extends Comparable<E>> {

        protected E value;
        protected TreeNode<E> left;
        protected TreeNode<E> right;

        public TreeNode(E value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

    }

}

Вывод

Before invert
Tree;
*****
  6
  3   4 
  7   3   8   1 

After invert
Tree;
*****
  6
  4   3 
  1   8   3   7 

Функция рекурсии может быть очень простой, как показано ниже:

public Node flipTree(Node node) {
    if(node == null) return null;

    Node left = flipTree(node.left);
    Node right = flipTree(node.right);

    node.left = right;
    node.right = left;

    return node;
}

 public class TreeNode
 {
     public int val;
     public TreeNode left;
     public TreeNode right;
     public TreeNode(int x) { val = x; }
 }

public class Solution
{
    public TreeNode root;
    public TreeNode InvertTree(TreeNode root)
    {
        if (root == null)
            return null;
        Swap(root);
        InvertTree(root.left);
        InvertTree(root.right);
        return root;
    }

    public void Swap(TreeNode root)
    {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
public class ReverseBinaryTree
{
    public void Test()
    {
        Solution tree = new Solution();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        tree.InvertTree(tree.root);
        Console.ReadLine();
    }
}

Я видел, что большинство ответов не фокусируются на проблемах нулевого указателя.

public static Node invertBinaryTree(Node node) {

    if(node != null) {
        Node temp = node.getLeftChild();

        node.setLeftChild(node.getRightChild());
        node.setRigthChild(temp);

        if(node.left!=null) { 
            invertBinaryTree(node.getLeftChild());
        }
        if(node.right !=null) {
            invertBinaryTree(node.getRightChild());
        }
    }

    return node;
}

В приведенном выше коде мы делаем рекурсивные вызовы только в том случае, если левый / правый потомок корневого узла не равен null. Это один из самых быстрых подходов!