LeetCode算法练习：验证二叉树是否对称

题目描述

给定一个二叉树，检查它是否是镜像对称的。具体来说，如果一棵树与其镜像相同，则认为它是对称的。

示例

示例 1：

输入: [1,2,2,3,4,4,3]
输出: true
解释:
      1
     / \
    2   2
   / \ / \
  3  4 4  3

示例 2：

输入: [1,2,2,null,3,null,3]
输出: false
解释:
      1
     / \
    2   2
     \   \
      3   3

解决方案

方法一：递归

递归方法通过比较左右子树来判断二叉树是否对称。具体实现如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return mirror(root->left, root->right);
    }

    bool mirror(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return (p->val == q->val) && mirror(p->left, q->right) && mirror(p->right, q->left);
    }
};

方法二：迭代

迭代方法使用栈来逐层比较左右子树。具体实现如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        stack tree;
        tree.push(root->left);
        tree.push(root->right);

        while (!tree.empty()) {
            TreeNode* p = tree.top(); tree.pop();
            TreeNode* q = tree.top(); tree.pop();

            if (!p && !q) continue;
            if (!p || !q) return false;
            if (p->val != q->val) return false;

            tree.push(p->left);
            tree.push(q->right);
            tree.push(p->right);
            tree.push(q->left);
        }
        return true;
    }
};

运行结果

以下是递归方法和迭代方法的运行结果截图：