Cách đảo ngược cây nhị phân tìm kiếm bằng đệ quy C#

Để đảo BST, gọi InvertABinarySearchTree với tham số node. Nếu null trả về null. Nếu không null, đệ quy đảo con trái và con phải, sau đó gán con phải cho con trái và ngược lại. Kết quả là cây gương của cây gốc.

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 Node InvertABinarySearchTree(Node node)
    {
        if (node == null)
        {
            return null;
        }
        Node left = InvertABinarySearchTree(node.LeftChild);
        Node right = InvertABinarySearchTree(node.RightChild);
        node.LeftChild = right;
        node.RightChild = left;
        return node; // Sửa: trả về node thay vì root
    }
}

Đầu vào

  1
 / \
3   2

Kết quả

  1
 / \
2   3

Giải thích: Đảo ngược (invert) cây nhị phân: hoán đổi con trái/phải tại mọi nút. Đệ quy post-order: đảo con trước, rồi hoán đổi tại nút hiện tại. Cây gốc và cây đảo là hình ảnh gương nhau. Lưu ý: code gốc trả về `root` (biến toàn cục), nên sửa thành `node`.