วิธีตรวจสอบว่า Tree เป็น Symmetric หรือไม่ด้วย Iterative ใน C#

ในแนวทาง Iterative เราต้องสร้าง 2 Queues หนึ่ง queue เก็บลูกซ้าย อีก queue เก็บค่าลูกขวา หาก tree ว่าง แล้วมัน symmetrical กับแกนแนวตั้งที่ผ่าน root node มิฉะนั้น ตรวจสอบว่าค่าที่ root node ของทั้งสอง subtree เหมือนกันหรือไม่ หากเหมือนกัน ตรวจสอบว่า left subtree และ right subtree เป็น symmetrical Enqueue ค่าลูกซ้ายและลูกขวาเข้า queue1 และ enqueue ลูกขวาและลูกซ้ายเข้า queue1

ตัวอย่าง

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 Q1 = new Queue();
        Queue Q2 = new Queue();
        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);
                Q1.Enqueue(n1.RightChild);
                Q1.Enqueue(n1.LeftChild);
            }
        }
        return true;
    }
}

ผลลัพธ์

    1
      2 2
     3 4 4 3 True