Cách kiểm tra cây đối xứng bằng phương pháp lặp C#

Phương pháp lặp: tạo 2 hàng đợi (Queue), một lưu con trái, một lưu con phải. Nếu cây rỗng → đối xứng. Kiểm tra giá trị gốc hai cây con. Nếu cùng giá trị, kiểm tra đối xứng của hai cây con. Enqueue con trái rồi con phải vào Q1, con phải rồi con trái vào Q2.

Ví dụ

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;
    }
}

Kết quả

      1
       2 2
      3 4 4 3
True

Giải thích: Kiểm tra đối xứng bằng BFS với 2 hàng đợi. Q1 duyệt theo thứ tự trái-phải, Q2 duyệt phải-trái. So sánh từng cặp nút lấy ra. Code gốc có lỗi enqueue trùng lặp (Q1.Enqueue RightChild 2 lần), đã sửa trong bản dịch. O(n) thời gian, O(w) không gian (độ rộng cây).