java-reversing-a-binary-tree
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で見つけることができます。]