1. Overview

1.概述

Reversing a binary tree is one of the problems that we might be asked to solve during a technical interview.

逆转二叉树是技术面试中可能被要求解决的问题之一。

In this quick tutorial, we’ll see a couple of different ways of solving this problem.

在这个快速教程中，我们将看到解决这个问题的几种不同方法。

2. Binary Tree

2.二进制树

A binary tree is a data structure in which each element has at most two children, which are referred to as the left child and the right child. The top element of the tree is the root node, whereas the children are the interior nodes.

二叉树是一种数据结构，其中每个元素最多拥有两个孩子，它们被称为左孩子和右孩子。树的顶端元素是根节点，而子节点是内部节点。

However, if a node has no child, it’s called a leaf.

然而，如果一个节点没有孩子，它就被称为叶子。

Having said that, let’s create our object that represents a node:

说到这里，让我们来创建代表一个节点的对象。

public class TreeNode {

    private int value;
    private TreeNode rightChild;
    private TreeNode leftChild;

    // Getters and setters

}

Then, let’s create our tree that we’ll be using in our examples:

然后，让我们创建我们的树，我们将在我们的例子中使用。

    TreeNode leaf1 = new TreeNode(1);
    TreeNode leaf2 = new TreeNode(3);
    TreeNode leaf3 = new TreeNode(6);
    TreeNode leaf4 = new TreeNode(9);

    TreeNode nodeRight = new TreeNode(7, leaf3, leaf4);
    TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2);

    TreeNode root = new TreeNode(4, nodeLeft, nodeRight);

In the previous method, we created the following structure:

在前面的方法中，我们创建了以下结构。

By reversing the tree from left to right, we’ll end up having the following structure:

通过将树从左到右颠倒过来，我们最终会有以下结构。

3. Reversing the Binary Tree

3.反转二叉树

3.1. Recursive Method

3.1.递归法

In the first example, we’ll use recursion to reverse the tree.

在第一个例子中，我们将使用递归来逆转树。

First of all, we’ll call our method using the tree’s root, then we’ll apply it on the left and the right children respectively until we reach the tree’s leaves:

首先，我们将使用树的根来调用我们的方法，然后我们将分别应用于左边和右边的孩子，直到我们到达树的叶子。

public void reverseRecursive(TreeNode treeNode) {
    if(treeNode == null) {
        return;
    }

    TreeNode temp = treeNode.getLeftChild();
    treeNode.setLeftChild(treeNode.getRightChild());
    treeNode.setRightChild(temp);

    reverseRecursive(treeNode.getLeftChild());
    reverseRecursive(treeNode.getRightChild());
}

3.2. Iterative Method

3.2.迭代法

In the second example, we’ll reverse the tree using an iterative approach. For that, we’re going to use a LinkedList, which we initialize with the root of our tree.

在第二个例子中，我们将使用迭代的方法来反转树。为此，我们将使用一个LinkedList，我们用树的根来初始化它。

Then, for every node we poll from the list, we add its children to that list before we permutate them.

然后，对于我们从列表中轮询的每个节点，我们在对其进行permutate之前将其子代加入该列表中。

We keep adding and removing from the LinkedList until we reach the tree’s leaves:

我们不断从LinkedList中添加和删除，直到我们到达树的叶子。

public void reverseIterative(TreeNode treeNode) {
    List<TreeNode> queue = new LinkedList<>();

    if(treeNode != null) {
        queue.add(treeNode);
    }

    while(!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if(node.getLeftChild() != null){
            queue.add(node.getLeftChild());
        }
        if(node.getRightChild() != null){
            queue.add(node.getRightChild());
        }

        TreeNode temp = node.getLeftChild();
        node.setLeftChild(node.getRightChild());
        node.setRightChild(temp);
    }
}

4. Conclusion

4.总结

In this quick article, we explored the two ways of reversing a binary tree. We have started by using a recursive method to reverse it. Then, we ended up using an iterative way to achieve the same result.

在这篇快速文章中，我们探讨了逆转二叉树的两种方法。我们首先使用了一种递归的方法来反转它。然后，我们最终使用了一种迭代的方式来实现同样的结果。

The complete source code of these examples and unit test cases can be found over on Github.

这些例子和单元测试案例的完整源代码可以在Github上找到。。