Cách kiểm tra cây đối xứng bằng đệ quy C#

Đệ quy: kiểm tra cây null → true. Gọi IsSymmetricMirror với con trái và con phải. Trong IsSymmetricMirror: cả hai null → true; một null → false; giá trị khác nhau → false; ngược lại đệ quy so sánh con trái của trái với con phải của phải, VÀ con phải của trái với con trái của phải.

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

Kết quả

      1
     / \
    2   2
   / \ / \
  3  4 4  3
True

Giải thích: Kiểm tra cây đối xứng (symmetric) qua trục gốc. So sánh cây con trái và phải như hình ảnh gương. Đệ quy so sánh: trái.trái với phải.phải, VÀ trái.phải với phải.trái. Cây ví dụ đối xứng hoàn hảo.