1. 概要

二分木の逆転は、技術面接中に解決するように求められる可能性のある問題の1つです。

このクイックチュートリアルでは、この問題を解決するためのいくつかの異なる方法を紹介します。

2. 二分木

二分木は、各要素に最大2つの子があり、左の子と右の子と呼ばれるデータ構造です。 ツリーの最上位要素はルートノードですが、子は内部ノードです。

ただし、ノードに子がない場合、それはリーフと呼ばれます。

そうは言っても、ノードを表すオブジェクトを作成しましょう。

public class TreeNode {

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

    // Getters and setters

}

次に、例で使用するツリーを作成しましょう。

    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);

前の方法では、次の構造を作成しました。

ツリーを左から右に反転すると、次の構造になります。

3. 二分木の反転

3.1. 再帰的方法

最初の例では、再帰を使用してツリーを反転します。

まず、ツリーのルートを使用してメソッドを呼び出し、次に、ツリーの葉に到達するまで、左と右の子にそれぞれ適用します。

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. 反復法

2番目の例では、反復アプローチを使用してツリーを反転します。そのために、ツリーのルートで初期化するLinkedListを使用します。

次に、リストからポーリングするすべてのノードについて、子を並べ替える前にその子をそのリストに追加します。

木の葉に到達するまで、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. 結論

この簡単な記事では、二分木を逆にする2つの方法について説明しました。 それを逆にするために再帰的な方法を使用することから始めました。 次に、同じ結果を達成するために反復的な方法を使用することになりました。

これらの例と単体テストケースの完全なソースコードは、Githubにあります。