剑指 Offer(第2版)面试题 28:对称的二叉树
- 剑指 Offer(第2版)面试题 28:对称的二叉树
- 解法1:递归
- 解法2:镜像二叉树 + 前序遍历
剑指 Offer(第2版)面试题 28:对称的二叉树
题目来源:39. 对称的二叉树
解法1:递归
递归判断两个子树是否互为镜像。
两个子树互为镜像当且仅当:
- 两个子树的根节点值相等。
- 第一棵子树的左子树和第二棵子树的右子树互为镜像,且第一棵子树的右子树和第二棵子树的左子树互为镜像。
代码:
/**
* 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 是二叉树的深度。