Javaでのバイナリツリーの反転

  • Java

  • link:/tag/data-structures/ [データ構造]

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);
前の方法では、次の構造を作成しました。
link:/uploads/tree.png []
ツリーを左から右に逆にすると、次の構造になります。
link:/uploads/tree2-1-100x89.png%20100w []

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つの方法を検討しました。 再帰的な方法を使用してそれを逆にすることから始めました。 それから、同じ結果を得るために反復的な方法を使用することになりました。
これらの例と単体テストケースの完全なソースコードhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-5[Githubで見つけることができます。]