C#の反復処理を使って木（ツリー）が対称かどうかを判定する方法

反復アプローチによる対称木の判定

反復（イテレーティブ）なアプローチでは、2つのキューを作成します。1つ目のキューは左側の子ノードを保存し、2つ目のキューは右側の子ノードを保存する役割を担います。

木が空である場合、その木は根ノードを通る垂直軸に対して対称であるとみなされ、true を返します。木が空でない場合は、まず両部分木の根ノードの値が一致しているかを確認します。値が一致していれば、さらに左部分木と右部分木が互いに対称（鏡像）であるかを順番に検証していきます。具体的には、キュー1には「左の子→右の子」の順で子ノードを追加し、キュー2には「右の子→左の子」の順で追加することで、左右を反転させた比較が可能になります。

アルゴリズムの手順

1. 根ノードが null の場合は true を返します（空の木は対称とみなされる）。
2. キューQ1に根の左の子を、キューQ2に根の右の子をそれぞれ追加します。
3. 両方のキューが空になるまで、次の処理を繰り返します。
   • 各キューからノードを1つずつ取り出します。
   • 片方だけが null の場合は false を返します。
   • 両方が null でない場合、値が異なれば false を返します。
   • Q1には左の子・右の子の順で、Q2には右の子・左の子の順で子ノードを追加します。
4. ループが正常に完了すれば、木は対称なので true を返します。

サンプルコード

public class TreesPgm{
    public class Node{
        public int Value;
        public Node LeftChild;
        public Node RightChild;
        public Node(int value){
            this.Value = value;
        }
        public override String ToString(){
            return "Node=" + Value;
        }
    }
    public bool IsSymmetricIterative(Node node){
        if (node == null){
            return true;
        }
        Queue<Node> q1 = new Queue<Node>();
        Queue<Node> q2 = new Queue<Node>();
        q1.Enqueue(node.LeftChild);
        q2.Enqueue(node.RightChild);
        while (q1.Count > 0 && q2.Count > 0){
            Node n1 = q1.Dequeue();
            Node n2 = q2.Dequeue();
            if ((n1 == null && n2 != null) || (n1 != null && n2 == null)){
                return false;
            }
            if (n1 != null){
                if (n1.Value != n2.Value){
                    return false;
                }
                q1.Enqueue(n1.LeftChild);
                q1.Enqueue(n1.RightChild);
                q2.Enqueue(n2.RightChild);
                q2.Enqueue(n2.LeftChild);
            }
        }
        return true;
    }
}

出力例

      1
    2    2
   3 4  4 3
True

この例では、木が左右で完全な鏡像構造になっているため、IsSymmetricIterative メソッドは True を返します。もし左右の値や構造が一致しないノードが存在した場合は、その時点で false が返されます。