由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 写了个symmetric tree的stack based iterative实现,有个bug
相关主题
Leetcode: Symmetric Tree有没有好的iterative的解法?G家电面
leetcode上Symmetric Tree这道题怎么用iterative的方法做?[leetcode] Maximum Depth of Binary Tree
请问怎么样才能想到关于tree等比较简洁的答案呢?同时记一下超慢速刷题过半以鼓励自己Interview question::
大牛帮我看看这哪错了? iterative inorder traversalGOOG ONSITE 面试
问一个题目Uni_value subtree problem
Time complexity求问一个Java问题
判断是不是binary search tree-leetcode这个inorder traversal 有错嘛,为什么leetcode 总报memory limit exceed?
hasPathSum热腾腾的 LinkedIn 电面题攒RP
相关话题的讨论汇总
话题: cur话题: treenode话题: null话题: root话题: left
进入JobHunting版参与讨论
1 (共1页)
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
4
对哦,没想到用preorder和直接对应。。。
1 (共1页)
进入JobHunting版参与讨论
相关主题
热腾腾的 LinkedIn 电面题攒RP问一个题目
帮我看一下5行代码Time complexity
Flatten Binary Tree to Linked List的recursive解法判断是不是binary search tree-leetcode
min depth binary tree用recursive解法一般能过关麽?hasPathSum
Leetcode: Symmetric Tree有没有好的iterative的解法?G家电面
leetcode上Symmetric Tree这道题怎么用iterative的方法做?[leetcode] Maximum Depth of Binary Tree
请问怎么样才能想到关于tree等比较简洁的答案呢?同时记一下超慢速刷题过半以鼓励自己Interview question::
大牛帮我看看这哪错了? iterative inorder traversalGOOG ONSITE 面试
相关话题的讨论汇总
话题: cur话题: treenode话题: null话题: root话题: left