大家都准备好了吗？# Living
j*x
1 楼
我觉得是有个bug，我还没想出来怎么构造反例，先不说具体的bug了
能过small和large case
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
stack lhs;
for (TreeNode* l_root = root; l_root != NULL; l_root = l_root->left)
{
lhs.push(l_root);
}
stack rhs;
for (TreeNode* r_root = root; r_root != NULL; r_root = r_root->right
) {
rhs.push(r_root);
}
while (!lhs.empty() && !rhs.empty()) {
TreeNode* l_cur = lhs.top();
lhs.pop();
TreeNode* r_cur = rhs.top();
rhs.pop();
if ((l_cur == NULL && r_cur != NULL)
|| (l_cur != NULL && r_cur == NULL)) {
return false;
}
if (l_cur->val != r_cur->val) {
return false;
}
for (l_cur = l_cur->right; l_cur != NULL; l_cur = l_cur->left) {
lhs.push(l_cur);
}
for (r_cur = r_cur->left; r_cur != NULL; r_cur = r_cur->right) {
rhs.push(r_cur);
}
}
return lhs.empty() && rhs.empty();
}
};
能过small和large case
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
stack
for (TreeNode* l_root = root; l_root != NULL; l_root = l_root->left)
{
lhs.push(l_root);
}
stack
for (TreeNode* r_root = root; r_root != NULL; r_root = r_root->right
) {
rhs.push(r_root);
}
while (!lhs.empty() && !rhs.empty()) {
TreeNode* l_cur = lhs.top();
lhs.pop();
TreeNode* r_cur = rhs.top();
rhs.pop();
if ((l_cur == NULL && r_cur != NULL)
|| (l_cur != NULL && r_cur == NULL)) {
return false;
}
if (l_cur->val != r_cur->val) {
return false;
}
for (l_cur = l_cur->right; l_cur != NULL; l_cur = l_cur->left) {
lhs.push(l_cur);
}
for (r_cur = r_cur->left; r_cur != NULL; r_cur = r_cur->right) {
rhs.push(r_cur);
}
}
return lhs.empty() && rhs.empty();
}
};
