C#で再帰を使って木構造（ツリー）が対称かどうかを判定する方法

木構造（ツリー）が対称であるかどうかを再帰的に判定する場合、まず対象の木が null かどうかを確認します。木が null であれば、それ自体が対称とみなされるため true を返します。

木が null でない場合は、isSymmetricMirror メソッドを呼び出します。このメソッド内では、左の子ノードと右の子ノードの値を比較し、以下のように判定を行います。

• 両方の子ノードが null の場合 → 対称（true）
• どちらか一方だけが null の場合 → 非対称（false）
• 両ノードの値が異なる場合 → 非対称（false）

上記のチェックを通過したら、左の子と右の子を交差させる形で引数に渡し、isSymmetricMirror メソッドを再帰的に呼び出します。これにより、木全体が鏡像関係にあるかどうかを効率的に検証できます。

サンプルコード

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 isSymmetricRecursive(Node node)
    {
        if (node == null){
            return true;
        }
        return isSymmetricMirror(node.LeftChild, node.RightChild);
    }
    private bool isSymmetricMirror(Node node1, Node node2){
        if (node1 == null && node2 == null){
            return true;
        }
        if (node1 == null || node2 == null){
            return false;
        }
        if (node1.Value != node2.Value){
            return false;
        }
        return isSymmetricMirror(node1.LeftChild, node2.RightChild) && isSymmetricMirror(node2.LeftChild, node1.RightChild);
    }
}

実行例

以下のような対称な二分木を用意した場合を考えます。

      1
    2   2
   3 4 4 3
True

この木は左右が鏡像の関係になっているため、isSymmetricRecursive メソッドの戻り値は True となります。

ポイントまとめ

• ルートが null なら対称とみなす
• 左右の子ノードを「外側同士・内側同士」で比較するのが鏡像判定の鍵
• 再帰によって各レベルの対称性を順次検証できる