logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
自信，就是“接受身体的缺点”
avatar
自信，就是“接受身体的缺点”# Joke - 肚皮舞运动
c*t
1 楼
我用两个stack, DFS比较,可是因为null无法进入stack，每次人前都要一堆if判断比较
，感觉很差。
有没有好点的iterative的解法？
多谢！
avatar
t*e
2 楼
裙子是H&M的，我配黑色tank
jacket是Martin & OSA的。
两件合在一起可能太大地了……所以jacket我会配深色牛仔或者其他深色裤子。
avatar
G*r
4 楼
太强大了
avatar
p*2
5 楼

BFS不行吗？

【在 c********t 的大作中提到】
: 我用两个stack, DFS比较,可是因为null无法进入stack，每次人前都要一堆if判断比较
: ，感觉很差。
: 有没有好点的iterative的解法？
: 多谢！
avatar
w*u
6 楼
ｓｆ～～～
avatar
c*7
8 楼
我在吃中饭。。。。。
avatar
c*t
9 楼
可以吧，可是一样一堆比较啊，有没有codes赏一个？

【在 p*****2 的大作中提到】
:
: BFS不行吗？
avatar
b*s
10 楼
虽然很模糊也不是全身，好像还是不错的嘛
记得去活动帖报到哦！

【在 t*****e 的大作中提到】
: 裙子是H&M的，我配黑色tank
: jacket是Martin & OSA的。
: 两件合在一起可能太大地了……所以jacket我会配深色牛仔或者其他深色裤子。
avatar
v*n
11 楼
这要问毕神医..
avatar
C*e
12 楼
标题很有哲理，受启发了
avatar
c*t
13 楼
贴个我的吧，一堆if, 大家轻拍
public boolean isSymmetric(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null) return true;

if(root.left == null && root.right == null) return true;
if(root.left == null || root.right == null) return false;

Stack s1= new Stack();
Stack s2= new Stack();


s1.push(root.left);
s2.push(root.right);

while(!s1.isEmpty() && !s2.isEmpty()){
TreeNode n1 = s1.pop();
TreeNode n2 = s2.pop();
if(n1==null && n2!=null) return false;
if(n1!=null && n2==null) return false;
if(n1.val != n2.val) return false;
if(n1.left==null && n2.right!=null) return false;
if(n1.right==null && n2.left !=null) return false;
if(n1.left!=null && n2.right==null) return false;
if(n1.right!=null && n2.left ==null) return false;
if(n1.left!=null) s1.push(n1.left);
if(n1.right!=null) s1.push(n1.right);
if(n2.right!=null) s2.push(n2.right);
if(n2.left!=null) s2.push(n2.left);
}

if(!s1.isEmpty() || !s2.isEmpty()) return false;
else return true;
}

【在 c********t 的大作中提到】
: 可以吧，可是一样一堆比较啊，有没有codes赏一个？
avatar
t*e
14 楼
为啥照片贴出来这么大，让我修改修改

【在 b*********s 的大作中提到】
: 虽然很模糊也不是全身，好像还是不错的嘛
: 记得去活动帖报到哦！
avatar
r*e
16 楼
你这是现场看得?

【在 G****r 的大作中提到】
: 太强大了
avatar
c*a
17 楼
这样行不行,inorder traverse和reverse inorder traverse.把结果存进data
structure里面，然后比较
我以前的做法是reverse tree然后比较
avatar
t*e
18 楼


【在 t*****e 的大作中提到】
: 裙子是H&M的，我配黑色tank
: jacket是Martin & OSA的。
: 两件合在一起可能太大地了……所以jacket我会配深色牛仔或者其他深色裤子。
avatar
b*3
19 楼
我用了两个que和1个stack，就没有多少null check，应该还可以优化。代码如下：
public boolean isSymmetric1(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null){
return true;
}else{
Queue que = new LinkedList();
Queue que1 = new LinkedList();
Stack st = new Stack();
que.add(root);
st.push(root);
while(que.size() > 0){
TreeNode tn = que.poll();
TreeNode tn1 = st.pop();
if(tn == null && tn1 == null){

}else if(tn == null || tn1 == null || tn.val != tn1.val){
return false;
}else {
que1.add(tn.left);
que1.add(tn.right);
}

if(que.size() == 0){
while(que1.size() > 0){
TreeNode tn2 = que1.poll();
que.add(tn2);
st.push(tn2);
}
}
}
return true;
}
}
avatar
t*e
20 楼


【在 t*****e 的大作中提到】
: 裙子是H&M的，我配黑色tank
: jacket是Martin & OSA的。
: 两件合在一起可能太大地了……所以jacket我会配深色牛仔或者其他深色裤子。
avatar
j*g
21 楼
你的代码稍微改改逻辑就不用那么多NULL判断了。C++写的，不太清楚java里对null的
处理。
class Solution {
public:
bool isSymmetric(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL)
return true;

stack s1;
stack s2;

s1.push(root->left);
s2.push(root->right);

while(!s1.empty()&& !s2.empty()){
TreeNode* n1 = s1.top();
TreeNode* n2 = s2.top();
s1.pop();
s2.pop();
if(n1==n2)
continue;
if(n1==NULL || n2 ==NULL)
return n1==n2;

if(n1->val != n2->val)
return false;

s1.push(n1->left);
s1.push(n1->right);
s2.push(n2->right);
s2.push(n2->left);
}

if(!s1.empty()||!s2.empty())
return false;
else
return true;
}
};

【在 c********t 的大作中提到】
: 贴个我的吧，一堆if, 大家轻拍
: public boolean isSymmetric(TreeNode root) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(root == null) return true;
:
: if(root.left == null && root.right == null) return true;
: if(root.left == null || root.right == null) return false;
:
: Stack s1= new Stack();
avatar
n*o
22 楼
真模糊啊。。。
avatar
p*2
23 楼
刚才看了一下ArrayList里边可以加null, 用两个arraylist ＋ BFS应该可以很简单的
完成了。
avatar
P*w
24 楼
白天重新拍照片
avatar
b*3
25 楼

这是jordandong的java版本，比我的前一种解法少用了一个stack，谢谢，代码如下：
public boolean isSymmetric(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null){
return true;
}else{
Queue que = new LinkedList();
Queue que1 = new LinkedList();
que.add(root.left);
que1.add(root.right);
while(que.size() > 0 && que1.size() > 0){
TreeNode tn = que.poll();
TreeNode tn1 = que1.poll();
if(tn == null && tn1 == null){
continue;
}else if(tn == null || tn1 == null || tn.val != tn1.val){
return false;
}else {
que.add(tn.left);
que.add(tn.right);
que1.add(tn1.right);
que1.add(tn1.left);
}
}
if(que.size() != 0 || que1.size() != 0){
return false;
}
return true;
}
}
avatar
t*e
26 楼
5555 找不到人帮我拍，所以只好自己对这镜子拍，好糊呀：（

【在 P**********w 的大作中提到】
: 白天重新拍照片
avatar
p*2
27 楼
public class Solution {
boolean isSym(ArrayList al)
{
int i=0;
int j=al.size()-1;
while(i{
if(al.get(i)==null || al.get(j)==null)
{
if(al.get(i)!=al.get(j)) return false;
}
else if(al.get(i).val!=al.get(j).val)
return false;
i++;
j--;
}
return true;
}

public boolean isSymmetric(TreeNode root)
{
ArrayList[] all=new ArrayList[2];
all[0]=new ArrayList();
all[1]=new ArrayList();

all[0].add(root);
int i=0;

while(all[i].size()>0)
{
if(!isSym(all[i])) return false;

int next=(i+1)%2;
all[next].clear();
for(TreeNode n : all[i])
{
if(n!=null)
{
all[next].add(n.left);
all[next].add(n.right);
}
}

i=next;
}

return true;
}
}
avatar
c*t
28 楼
这个好，用bfs， Queue,LinkedList可以入null,省去烦恼

下：

【在 b*******3 的大作中提到】
:
: 这是jordandong的java版本，比我的前一种解法少用了一个stack，谢谢，代码如下：
: public boolean isSymmetric(TreeNode root) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(root == null){
: return true;
: }else{
: Queue que = new LinkedList();
: Queue que1 = new LinkedList();
avatar
c*t
29 楼
土了，发现原来java stack和queue都允许null,只是我自己代码开始逻辑有问题。修改
后的DFS如下,过了。
public boolean isSymmetric2(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if (root == null)
return true;
Stack s1 = new Stack();
Stack s2 = new Stack();
s1.push(root.left);
s2.push(root.right);
while (!s1.isEmpty() && !s2.isEmpty()) {
TreeNode n1 = s1.pop();
TreeNode n2 = s2.pop();
if (n1 == null && n2 == null)
continue;
else if (n1 == null || n2 == null || n1.val != n2.val)
return false;
else {
s1.push(n1.left);
s1.push(n1.right);
s2.push(n2.right);
s2.push(n2.left);
}
}
if (!s1.isEmpty() || !s2.isEmpty())
return false;
else
return true;
}

【在 p*****2 的大作中提到】
: public class Solution {
: boolean isSym(ArrayList al)
: {
: int i=0;
: int j=al.size()-1;
: while(i: {
: if(al.get(i)==null || al.get(j)==null)
: {
: if(al.get(i)!=al.get(j)) return false;
avatar
c*t
30 楼
我用两个stack, DFS比较,可是因为null无法进入stack，每次人前都要一堆if判断比较
，感觉很差。
有没有好点的iterative的解法？
多谢！
avatar
p*2
31 楼

BFS不行吗？

【在 c********t 的大作中提到】
: 我用两个stack, DFS比较,可是因为null无法进入stack，每次人前都要一堆if判断比较
: ，感觉很差。
: 有没有好点的iterative的解法？
: 多谢！
avatar
c*t
32 楼
可以吧，可是一样一堆比较啊，有没有codes赏一个？

【在 p*****2 的大作中提到】
:
: BFS不行吗？
avatar
c*t
33 楼
贴个我的吧，一堆if, 大家轻拍
public boolean isSymmetric(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null) return true;

if(root.left == null && root.right == null) return true;
if(root.left == null || root.right == null) return false;

Stack s1= new Stack();
Stack s2= new Stack();


s1.push(root.left);
s2.push(root.right);

while(!s1.isEmpty() && !s2.isEmpty()){
TreeNode n1 = s1.pop();
TreeNode n2 = s2.pop();
if(n1==null && n2!=null) return false;
if(n1!=null && n2==null) return false;
if(n1.val != n2.val) return false;
if(n1.left==null && n2.right!=null) return false;
if(n1.right==null && n2.left !=null) return false;
if(n1.left!=null && n2.right==null) return false;
if(n1.right!=null && n2.left ==null) return false;
if(n1.left!=null) s1.push(n1.left);
if(n1.right!=null) s1.push(n1.right);
if(n2.right!=null) s2.push(n2.right);
if(n2.left!=null) s2.push(n2.left);
}

if(!s1.isEmpty() || !s2.isEmpty()) return false;
else return true;
}

【在 c********t 的大作中提到】
: 可以吧，可是一样一堆比较啊，有没有codes赏一个？
avatar
c*a
34 楼
这样行不行,inorder traverse和reverse inorder traverse.把结果存进data
structure里面，然后比较
我以前的做法是reverse tree然后比较
avatar
b*3
35 楼
我用了两个que和1个stack，就没有多少null check，应该还可以优化。代码如下：
public boolean isSymmetric1(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null){
return true;
}else{
Queue que = new LinkedList();
Queue que1 = new LinkedList();
Stack st = new Stack();
que.add(root);
st.push(root);
while(que.size() > 0){
TreeNode tn = que.poll();
TreeNode tn1 = st.pop();
if(tn == null && tn1 == null){

}else if(tn == null || tn1 == null || tn.val != tn1.val){
return false;
}else {
que1.add(tn.left);
que1.add(tn.right);
}

if(que.size() == 0){
while(que1.size() > 0){
TreeNode tn2 = que1.poll();
que.add(tn2);
st.push(tn2);
}
}
}
return true;
}
}
avatar
j*g
36 楼
你的代码稍微改改逻辑就不用那么多NULL判断了。C++写的，不太清楚java里对null的
处理。
class Solution {
public:
bool isSymmetric(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL)
return true;

stack s1;
stack s2;

s1.push(root->left);
s2.push(root->right);

while(!s1.empty()&& !s2.empty()){
TreeNode* n1 = s1.top();
TreeNode* n2 = s2.top();
s1.pop();
s2.pop();
if(n1==n2)
continue;
if(n1==NULL || n2 ==NULL)
return n1==n2;

if(n1->val != n2->val)
return false;

s1.push(n1->left);
s1.push(n1->right);
s2.push(n2->right);
s2.push(n2->left);
}

if(!s1.empty()||!s2.empty())
return false;
else
return true;
}
};

【在 c********t 的大作中提到】
: 贴个我的吧，一堆if, 大家轻拍
: public boolean isSymmetric(TreeNode root) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(root == null) return true;
:
: if(root.left == null && root.right == null) return true;
: if(root.left == null || root.right == null) return false;
:
: Stack s1= new Stack();
avatar
p*2
37 楼
刚才看了一下ArrayList里边可以加null, 用两个arraylist ＋ BFS应该可以很简单的
完成了。
avatar
b*3
38 楼

这是jordandong的java版本，比我的前一种解法少用了一个stack，谢谢，代码如下：
public boolean isSymmetric(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null){
return true;
}else{
Queue que = new LinkedList();
Queue que1 = new LinkedList();
que.add(root.left);
que1.add(root.right);
while(que.size() > 0 && que1.size() > 0){
TreeNode tn = que.poll();
TreeNode tn1 = que1.poll();
if(tn == null && tn1 == null){
continue;
}else if(tn == null || tn1 == null || tn.val != tn1.val){
return false;
}else {
que.add(tn.left);
que.add(tn.right);
que1.add(tn1.right);
que1.add(tn1.left);
}
}
if(que.size() != 0 || que1.size() != 0){
return false;
}
return true;
}
}
avatar
p*2
39 楼
public class Solution {
boolean isSym(ArrayList al)
{
int i=0;
int j=al.size()-1;
while(i{
if(al.get(i)==null || al.get(j)==null)
{
if(al.get(i)!=al.get(j)) return false;
}
else if(al.get(i).val!=al.get(j).val)
return false;
i++;
j--;
}
return true;
}

public boolean isSymmetric(TreeNode root)
{
ArrayList[] all=new ArrayList[2];
all[0]=new ArrayList();
all[1]=new ArrayList();

all[0].add(root);
int i=0;

while(all[i].size()>0)
{
if(!isSym(all[i])) return false;

int next=(i+1)%2;
all[next].clear();
for(TreeNode n : all[i])
{
if(n!=null)
{
all[next].add(n.left);
all[next].add(n.right);
}
}

i=next;
}

return true;
}
}
avatar
c*t
40 楼
这个好，用bfs， Queue,LinkedList可以入null,省去烦恼

下：

【在 b*******3 的大作中提到】
:
: 这是jordandong的java版本，比我的前一种解法少用了一个stack，谢谢，代码如下：
: public boolean isSymmetric(TreeNode root) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(root == null){
: return true;
: }else{
: Queue que = new LinkedList();
: Queue que1 = new LinkedList();
avatar
c*t
41 楼
土了，发现原来java stack和queue都允许null,只是我自己代码开始逻辑有问题。修改
后的DFS如下,过了。
public boolean isSymmetric2(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if (root == null)
return true;
Stack s1 = new Stack();
Stack s2 = new Stack();
s1.push(root.left);
s2.push(root.right);
while (!s1.isEmpty() && !s2.isEmpty()) {
TreeNode n1 = s1.pop();
TreeNode n2 = s2.pop();
if (n1 == null && n2 == null)
continue;
else if (n1 == null || n2 == null || n1.val != n2.val)
return false;
else {
s1.push(n1.left);
s1.push(n1.right);
s2.push(n2.right);
s2.push(n2.left);
}
}
if (!s1.isEmpty() || !s2.isEmpty())
return false;
else
return true;
}

【在 p*****2 的大作中提到】
: public class Solution {
: boolean isSym(ArrayList al)
: {
: int i=0;
: int j=al.size()-1;
: while(i: {
: if(al.get(i)==null || al.get(j)==null)
: {
: if(al.get(i)!=al.get(j)) return false;
avatar
a*8
42 楼
#include
using namespace std;
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if(NULL == root) return true;
queue q;
q.push(root->left);
q.push(root->right);
while(!q.empty()) {
TreeNode *left = q.front();
q.pop();
TreeNode *right = q.front();
q.pop();
if(NULL == left && NULL == right)
continue;
if(left && right) {
if(left->val != right->val)
return false;
q.push(left->left);
q.push(right->right);
q.push(left->right);
q.push(right->left);
continue;
}
return false;
}
}
};
avatar
t*a
43 楼
这题为什么大家不用递归呢，会很漂亮的啊。
(defn is-symmetric?
([[lft value rgt]]
(is-symmetric? lft rgt))
([lft rgt]
(cond (and (nil? lft) (nil? rgt)) true
(or (nil? lft) (nil? rgt)) false
:else (let [[l1 v1 r1] lft
[l2 v2 r2] rgt]
(and (== v1 v2) (is-symmetric? l1 r2) (is-symmetric? l2
r1))))))
(is-symmetric? [[[nil 3 nil] 2 [nil 4 nil]] 1 [[nil 4 nil] 2 [nil 3 nil]]])
; true
(is-symmetric? [[nil 2 [nil 3 nil]] 1 [nil 2 [nil 3 nil]]]) ; false
avatar
t*a
44 楼
iterative solution:
函数is-symmetric-level评估每一层的value，检查是否是symmetric的。
函数bfs-step执行一步breath first search，返回下一层所有节点，包括nil在内
函数is-symmetric-iterative?迭代bfs-step直到某层所有节点为nil。之后从上到下检
查每一层。
(defn is-symmetric-level? [trees]
(let [values (map #(if (nil? %)
nil
(let [[l v r] %] v)) trees)]
(= values (reverse values))))
(defn bfs-step [trees]
(let [subtrees (mapcat #(if (nil? %)
[nil nil]
(let [[l v r] %] [l r])) trees)]
subtrees))
(defn is-symmetric-iterative? [tree]
(every? true? (map is-symmetric-level? (take-while #(not-every? nil? %) (
iterate bfs-step [tree])))))
(is-symmetric-iterative? [[[nil 3 nil] 2 [nil 4 nil]] 1 [[nil 4 nil] 2 [nil
3 nil]]]) ; true
(is-symmetric-iterative? [[nil 2 [nil 3 nil]] 1 [nil 2 [nil 3 nil]]]) ;
false
avatar
o*1
46 楼
class Solution {
public:
bool isSymmetric(TreeNode *root) {
std::vector stack, buf;
std::vector::iterator it, ite;
if (!root)
return true;
stack.push_back(root->left);
stack.push_back(root->right);

while (stack.size()) {
if (stack.size() % 2)
return false;

it = stack.begin();
ite = it + 1;
while (it < stack.end()) {
TreeNode *left = *it;
TreeNode *right = *ite;
if ((!left && right) || (left && !right))
return false;
if ((left && right) && (left->val != right->val))
return false;
if (left && right) {
buf.push_back(left->left);
buf.push_back(right->right);
buf.push_back(left->right);
buf.push_back(right->left);
}
it += 2;
ite += 2;
}
swap(stack, buf);
buf.clear();
}
return true;
}
};
avatar
h*3
47 楼
can only pass 17/28 test cases.

下：

【在 b*******3 的大作中提到】
:
: 这是jordandong的java版本，比我的前一种解法少用了一个stack，谢谢，代码如下：
: public boolean isSymmetric(TreeNode root) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(root == null){
: return true;
: }else{
: Queue que = new LinkedList();
: Queue que1 = new LinkedList();
avatar
G*A
48 楼
scan tree twice.
第一遍: in-order (left to right),第二遍: in-order (right to left),然后比较两
次遍历的结果。

【在 c********t 的大作中提到】
: 我用两个stack, DFS比较,可是因为null无法进入stack，每次人前都要一堆if判断比较
: ，感觉很差。
: 有没有好点的iterative的解法？
: 多谢！
avatar
s*e
49 楼
bool isSymmetricTree(TreeNode* root){
queue q1, q2, p1, p2;
if(!root) return true;
if((!root->left) && (!root->right)) return true;
if(!(root->left && root->right && (root->left->val == root->right->val)))
return false;
q1.push(root->left);
q2.push(root->right);
TreeNode* t1;
TreeNode* t2;
while(!q1.empty()){
while(!q1.empty()){
t1=q1.front();
t2=q2.front();
q1.pop();
q2.pop();
if(t1->left && t2->right && (t1->left->val == t2->right->val)){
p1.push(t1->left);
p2.push(t2->right);
} else if(!(t1->left == NULL && t2->right == NULL)) return false;
if(t2->left && t1->right && (t2->left->val == t1->right->val)){
p1.push(t2->left);
p2.push(t1->right);
} else if(!(t2->left == NULL && t1->right == NULL)) return false;
}
if(!q2.empty()) return false;
swap(q1, p1);
swap(q2, p2);
}
if(!q2.empty()) return false;
return true;
}
相关阅读
臭笑话：世界堕落，无齿装鼻。赵大兰嫁不嫁人傻，钱多，又有人骗左派的钱了 (转载)天字一号大傻逼真的假的，地铁列车前面翻筋斗所以不能在饭桌上打架幽默笑话：兄弟，是不是发现你媳妇和老王的事了 zz引力是怎么来的？我擦fremont 的枪店被抢了 (转载)Re: OSU老大娘对凶手的关爱 (转载)小六和得体郎发表的帖子，我整理了下，对话很精彩 (转载)我发现将军们和器人谈笑风生啊怎么觉得有点不对哈哈 Mr. Pepper才帝的老同学的女儿四岁小正太一枚的神补刀 Zz希拉里开始着手准备第三次参选 (转载)车子好久没洗了，一层灰，今天停在店门口 zz挥挥手，不带走一片云彩 (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。