c********t 发帖数: 5706 | 1 我用两个stack, DFS比较,可是因为null无法进入stack,每次人前都要一堆if判断比较
,感觉很差。
有没有好点的iterative的解法?
多谢! |
p*****2 发帖数: 21240 | 2
BFS不行吗?
【在 c********t 的大作中提到】 : 我用两个stack, DFS比较,可是因为null无法进入stack,每次人前都要一堆if判断比较 : ,感觉很差。 : 有没有好点的iterative的解法? : 多谢!
|
c********t 发帖数: 5706 | 3 可以吧,可是一样一堆比较啊,有没有codes赏一个?
【在 p*****2 的大作中提到】 : : BFS不行吗?
|
c********t 发帖数: 5706 | 4 贴个我的吧,一堆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赏一个?
|
c*****a 发帖数: 808 | 5 这样行不行,inorder traverse和reverse inorder traverse.把结果存进data
structure里面,然后比较
我以前的做法是reverse tree然后比较 |
b*******3 发帖数: 145 | 6 我用了两个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;
}
} |
j********g 发帖数: 80 | 7 你的代码稍微改改逻辑就不用那么多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();
|
p*****2 发帖数: 21240 | 8 刚才看了一下ArrayList里边可以加null, 用两个arraylist + BFS应该可以很简单的
完成了。 |
b*******3 发帖数: 145 | 9
这是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;
}
} |
p*****2 发帖数: 21240 | 10 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;
}
} |
|
|
c********t 发帖数: 5706 | 11 这个好,用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();
|
c********t 发帖数: 5706 | 12 土了,发现原来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;
|
c********t 发帖数: 5706 | 13 我用两个stack, DFS比较,可是因为null无法进入stack,每次人前都要一堆if判断比较
,感觉很差。
有没有好点的iterative的解法?
多谢! |
p*****2 发帖数: 21240 | 14
BFS不行吗?
【在 c********t 的大作中提到】 : 我用两个stack, DFS比较,可是因为null无法进入stack,每次人前都要一堆if判断比较 : ,感觉很差。 : 有没有好点的iterative的解法? : 多谢!
|
c********t 发帖数: 5706 | 15 可以吧,可是一样一堆比较啊,有没有codes赏一个?
【在 p*****2 的大作中提到】 : : BFS不行吗?
|
c********t 发帖数: 5706 | 16 贴个我的吧,一堆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赏一个?
|
c*****a 发帖数: 808 | 17 这样行不行,inorder traverse和reverse inorder traverse.把结果存进data
structure里面,然后比较
我以前的做法是reverse tree然后比较 |
b*******3 发帖数: 145 | 18 我用了两个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;
}
} |
j********g 发帖数: 80 | 19 你的代码稍微改改逻辑就不用那么多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();
|
p*****2 发帖数: 21240 | 20 刚才看了一下ArrayList里边可以加null, 用两个arraylist + BFS应该可以很简单的
完成了。 |
|
|
b*******3 发帖数: 145 | 21
这是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;
}
} |
p*****2 发帖数: 21240 | 22 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;
}
} |
c********t 发帖数: 5706 | 23 这个好,用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();
|
c********t 发帖数: 5706 | 24 土了,发现原来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;
|
a*********8 发帖数: 17 | 25 #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;
}
}
}; |
t****a 发帖数: 1212 | 26 这题为什么大家不用递归呢,会很漂亮的啊。
(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 |
t****a 发帖数: 1212 | 27 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 |
y******e 发帖数: 8 | |
o*******1 发帖数: 2 | 29 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;
}
}; |
h******3 发帖数: 351 | 30 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();
|
|
|
G****A 发帖数: 4160 | 31 scan tree twice.
第一遍: in-order (left to right),第二遍: in-order (right to left),然后比较两
次遍历的结果。
【在 c********t 的大作中提到】 : 我用两个stack, DFS比较,可是因为null无法进入stack,每次人前都要一堆if判断比较 : ,感觉很差。 : 有没有好点的iterative的解法? : 多谢!
|
s****e 发帖数: 75 | 32 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;
} |