剑指 Offer（第2版）面试题 28：对称的二叉树

题目来源：39. 对称的二叉树

解法1：递归

递归判断两个子树是否互为镜像。

两个子树互为镜像当且仅当：

1. 两个子树的根节点值相等。
2. 第一棵子树的左子树和第二棵子树的右子树互为镜像，且第一棵子树的右子树和第二棵子树的左子树互为镜像。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution
{
public:bool isSymmetric(TreeNode *root){// 特判，空树是对称的二叉树if (root == nullptr)return true;return dfs(root->left, root->right);}bool dfs(TreeNode *root1, TreeNode *root2){if (root1 == nullptr && root2 == nullptr)return true;if ((root1 && root2 == nullptr) || (root1 == nullptr && root2))return false;if (root1->val != root2->val)return false;return dfs(root1->left, root2->right) && dfs(root1->right, root2->left);}
};

复杂度分析：

时间复杂度：O(n)，其中 n 是二叉树的节点数。

空间复杂度：O(depth)，其中 depth 是二叉树的深度。极端情况下栈的深度将达到 O(n)。

解法2：镜像二叉树 + 前序遍历

我们发现：如果一个二叉树是对称的，则它的前序遍历序列和它的镜像二叉树的前序遍历序列相同。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution
{
public:bool isSymmetric(TreeNode *root){if (root == nullptr)return true;vector<int> preOrderSequence, mirrorPreOrderSequence;preOrder(root, preOrderSequence);mirror(root);preOrder(root, mirrorPreOrderSequence);return preOrderSequence == mirrorPreOrderSequence;}// 辅函数 - 镜像void mirror(TreeNode *root){if (root == nullptr)return;if (root->left == nullptr && root->right == nullptr)return;if (root->left)mirror(root->left);if (root->right)mirror(root->right);// swap(root->left, root->right)TreeNode *temp = root->left;root->left = root->right;root->right = temp;}// 辅函数 - 前序遍历void preOrder(TreeNode *root, vector<int> &nums){if (root == nullptr){nums.push_back(-1);return;}nums.push_back(root->val);preOrder(root->left, nums);preOrder(root->right, nums);}
};

复杂度分析：

时间复杂度：O(n)，其中 n 是二叉树的节点个数。原树中每个节点仅被遍历一次。

空间复杂度：O(depth)，其中 depth 是二叉树的深度。