非对称二叉树
对称二叉树 - 图1

对称二叉树
对称二叉树 - 图2

递归实现

  1. // 对称二叉树判断 - 递归实现
  2. public static bool SymmetricBinaryTree(Node root)
  3. {
  4.     return Mirror(root.left, root.right);
  5. }
  7. public static bool Mirror(Node left, Node right)
  8. {
  9.     // 如果左节点、右节点都为空
  10.     if (left == null && right == null) return true;
  12.     // 如果只有一个节点，或者有两个节点，但是两个节点值不相等
  13.     if (left == null || right == null || left.value != right.value) return false;
  15.     // 左节点的左孩子和右节点的右孩子比较，左节点的右孩子和右节点的左孩子比较
  16.     return Mirror(left.left, right.right) && Mirror(left.right, right.left);
  17. }

非递归实现

我们可以建立一个队列，每次按顺序将一对需要比较的结点放进去，比较完之后再出列，再进行下一对的比较。

// 对称二叉树判断 - 非递归实现
public static bool SymmetricBinaryTree2(Node root)
{
    if (root == null) return true;

    Queue<Node> queue = new Queue<Node>();
    Node left, right;

    queue.Enqueue(root.left);
    queue.Enqueue(root.right);

    while(queue.Count > 0)
    {
        // 每两个出队
        left = queue.Dequeue();
        right = queue.Dequeue();

        // 如果都为空继续循环
        if (left == null && right == null)
            continue;

        // 如果只有一个节点，或者有两个节点，但是两个节点值不相等
        if (left == null || right == null || left.value != right.value)
            return false;

        // 入栈顺序：左节点的左孩子，右节点的右孩子；左节点的右孩子、右节点的左孩子
        queue.Enqueue(left.left);
        queue.Enqueue(right.right);
        queue.Enqueue(left.right);
        queue.Enqueue(right.left);
    }

    return true;
}