二分木の反転方法

二分木の反転とは何か？まず最初に、二分木の反転とはどのような操作なのかを説明します。二分木の反転とは、各ノードの左右の子ノードを入れ替える操作のことです。つまり、二分木の左右の子ノードを反転させることで、木の形状が逆になります。

二分木の反転のアルゴリズム二分木を反転するための基本的なアルゴリズムは、再帰的な方法と反復的な方法の2つがあります。

a. 再帰的な方法: 二分木を再帰的に反転させるためには、各ノードの左右の子ノードを入れ替えます。そして、各子ノードに対して同じ操作を再帰的に行います。

以下は、再帰的な方法で二分木を反転するJavaのコード例です。

  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;

      TreeNode(int val) {
          this.val = val;
      }
  }

  public class BinaryTreeInverter {

      public TreeNode invertTree(TreeNode root) {
          if (root == null) {
              return null;
          }

          TreeNode left = invertTree(root.left);
          TreeNode right = invertTree(root.right);

          root.left = right;
          root.right = left;

          return root;
      }
  }

b. 反復的な方法: 反復的な方法では、スタックやキューを使用して二分木をトラバースしながら、各ノードの左右の子ノードを入れ替えます。

以下は、反復的な方法で二分木を反転するJavaのコード例です。

  import java.util.Stack;

  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;

      TreeNode(int val) {
          this.val = val;
      }
  }

  public class BinaryTreeInverter {

      public TreeNode invertTree(TreeNode root) {
          if (root == null) {
              return null;
          }

          Stack<TreeNode> stack = new Stack<>();
          stack.push(root);

          while (!stack.isEmpty()) {
              TreeNode node = stack.pop();
              TreeNode temp = node.left;
              node.left = node.right;
              node.right = temp;

              if (node.left != null) {
                  stack.push(node.left);
              }

              if (node.right != null) {
                  stack.push(node.right);
              }
          }

          return root;
      }
  }

以上が、Javaで二分木を反転するためのいくつかの方法とコード例です。これらの方法を使って、二分木を反転させることができます。