Leetcode: Symmetric Tree
Leetcode: Symmetric Tree
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 17:28:51
发布于 2019-01-22 17:28:51
题目：
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3But the following is not:
1
/ \
2 2
\ \
3 3Note: Bonus points if you could solve it both recursively and iteratively.
思路分析：
题目要求分别用递归和迭代的方法进行。递归这里不说了，直接看代码。迭代算法可以使用C++标准库中的deque数据结构，允许从前面和后面操作元素。
递归算法：
class Solution
{
private:
bool checkSymmetric(TreeNode *left, TreeNode *right)
{
if (left == NULL && right == NULL)
{
return true;
}
else if (left && right && left->val == right->val)
{
return checkSymmetric(left->left, right->right) && checkSymmetric(left->right, right->left);
}
else
{
return false;
}
}
public:
bool isSymmetric(TreeNode *root)
{
if (root == NULL)
{
return true;
}
else
{
return checkSymmetric(root->left, root->right);
}
}
};迭代算法（使用deque结构）：
class Solution
{
public:
bool isSymmetric(TreeNode *root)
{
if (!root)
{
return true;
}
//如果左右子树都为NULL
if (!root->left && !root->right)
{
return true;
}
//左右子树一个为NULL一个不为NULL
if ((root->left && !root->right) || (!root->left && root->right))
{
return false;
}
//左右子树都不为NULL
TreeNode *leftNode, *rightNode;
deque<TreeNode*> nodeDeque;
nodeDeque.push_front(root->left);
nodeDeque.push_back(root->right);
while (!nodeDeque.empty())
{
leftNode = nodeDeque.front();
rightNode = nodeDeque.back();
nodeDeque.pop_front();
nodeDeque.pop_back();
if (leftNode->val != rightNode->val)
{
return false;
}
if ((leftNode->left && !rightNode->right) || (!leftNode->left && rightNode->right))
{
return false;
}
if (leftNode->left)
{
nodeDeque.push_front(leftNode->left);
nodeDeque.push_back(rightNode->right);
}
if ((leftNode->right && !rightNode->left) || (!leftNode->right && rightNode->left))
{
return false;
}
if (leftNode->right)
{
nodeDeque.push_front(leftNode->right);
nodeDeque.push_back(rightNode->left);
}
}
return true;
}
};我看了下，使用递归算法在Leetcode上提交是8ms，使用迭代算法是10ms。
网上有的说采用中序遍历，判断遍历的结果对称就OK了。实际上这是不行的。
class Solution
{
private:
void inOrder(TreeNode *node, vector<int> &result)
{
if (node)
{
inOrder(node->left, result);
result.push_back(node->val);
inOrder(node->right, result);
}
}
public:
bool isSymmetric(TreeNode *root)
{
if (root == NULL)
{
return true;
}
vector<int> result;
inOrder(root, result);
vector<int>::size_type size = result.size();
bool flag = true;
for (int i = 0, j = size - 1; i < j; i++, j--)
{
if (result[i] != result[j])
{
flag = false;
break;
}
}
return flag;
}
};这样的程序在比如{1， 2， 3， 3，#， 2}这样的测试用例就不能通过。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年03月11日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读