Joyce' Blog
0%

symmetric-tree

发表于

题目描述

给定一个二叉树，检查它是否是镜像对称的。运用递归和迭代两种方法解决这个问题。

题解

递归：

1
2
3
4
5
6
7
8
9
10
bool compare(TreeNode* tree1, TreeNode* tree2)
{
	if (tree1 == NULL && tree2 == NULL) return true;
    if (tree1 == NULL || tree2 == NULL) return false;
	return tree1->val == tree2->val && compare(tree1->left, tree2->right) && compare(tree1->right, tree2->left);
}
bool isSymmetric(TreeNode* root) {
	if (!root)return true;
	return compare(root->left, root->right);
}

执行用时 :4 ms, 在所有 C++ 提交中击败了92.79%的用户

内存消耗 :14.3 MB, 在所有 C++ 提交中击败了100.00%的用户

既然递归这么省事，为什么还要写迭代。

迭代：

用到了队列的结构，注意一下左右子树压入的顺序就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isSymmetric2(TreeNode* root)
{
	if (!root)return true;
	TreeNode* left = root->left;
	TreeNode* right = root->right;
	queue<TreeNode*> q;
	q.push(left);
	q.push(right);
	while (!q.empty())
	{
		left = q.front();
		q.pop();
		right = q.front();
		q.pop();
		if (left == NULL && right == NULL)continue;
		if (left == NULL || right == NULL)return false;
		if (left->val != right->val)return false;
		q.push(left->left);
		q.push(right->right);
		q.push(left->right);
		q.push(right->left);
	}
	return true;
}