j********x
发帖数: 2330 | 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();
}
}; | j********x
发帖数: 2330 | 2 如果一个树的全部节点值都一样，上面这个无论任何情况都会给出true的答案 | b******7
发帖数: 92 | 3 实现得复杂了，stack中存pair简单点
bool isSymmetric(TreeNode *root) {
if(root == NULL) return true;
stack > s;
s.push(make_pair(root->left,root->right));
while(!s.empty())
{
pair cur = s.top();
s.pop();
if(cur.first == NULL && cur.second == NULL)
continue;
else if(cur.first == NULL || cur.second == NULL || cur.first->
val != cur.second->val)
return false;
else
{
s.push(make_pair(cur.first->left,cur.second->right));
s.push(make_pair(cur.first->right,cur.second->left));
}
}
return true;
}
【在 j********x 的大作中提到】
: 我觉得是有个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) {}
: * };
| j********x
发帖数: 2330 | |
|
