由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Leetcode: Symmetric Tree有没有好的iterative的解法?
相关主题
leetcode上Symmetric Tree这道题怎么用iterative的方法做?how many ways can you paint a cube using 3 colors?
写了个symmetric tree的stack based iterative实现,有个buggeneral solution for missing number(s) problem
请问怎么样才能想到关于tree等比较简洁的答案呢?同时记一下超慢速刷题过半以鼓励自己求一道题的解答
新鲜出炉的amazon面经-phone&onsiteAmazon面经
Job Opening in DC area报一个amazon的offer及面经
通讯公司招software engineer问个resume里一项skill的问题。A家第二轮电面
矩阵A 满足 A+A'=C, where C is a constant (转载)请教个题
谁给个不是brute force的解法面试题讨论,最优解
相关话题的讨论汇总
话题: treenode话题: null话题: return话题: false话题: root
进入JobHunting版参与讨论
1 (共1页)
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;
}
}
相关主题
通讯公司招software engineerhow many ways can you paint a cube using 3 colors?
矩阵A 满足 A+A'=C, where C is a constant (转载)general solution for missing number(s) problem
谁给个不是brute force的解法求一道题的解答
进入JobHunting版参与讨论
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应该可以很简单的
完成了。
相关主题
Amazon面经请教个题
报一个amazon的offer及面经面试题讨论,最优解
问个resume里一项skill的问题。A家第二轮电面面试题-牙签压线的几率
进入JobHunting版参与讨论
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
28
https://github.com/patrickyao1988/LeetCode-OJ/blob/master/SymmetricTree.java
#L58
基本思路就是BFS检查每一层,只用2个queue,一个检查当前这层是否对称,一个存储
下一层节点。
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();

相关主题
Security 面試問題写了个symmetric tree的stack based iterative实现,有个bug
我太笨了啊,我现在无法保证每天刷一道Leetcode的题目啊请问怎么样才能想到关于tree等比较简洁的答案呢?同时记一下超慢速刷题过半以鼓励自己
leetcode上Symmetric Tree这道题怎么用iterative的方法做?新鲜出炉的amazon面经-phone&onsite
进入JobHunting版参与讨论
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;
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
面试题讨论,最优解Job Opening in DC area
面试题-牙签压线的几率通讯公司招software engineer
Security 面試問題矩阵A 满足 A+A'=C, where C is a constant (转载)
我太笨了啊,我现在无法保证每天刷一道Leetcode的题目啊谁给个不是brute force的解法
leetcode上Symmetric Tree这道题怎么用iterative的方法做?how many ways can you paint a cube using 3 colors?
写了个symmetric tree的stack based iterative实现,有个buggeneral solution for missing number(s) problem
请问怎么样才能想到关于tree等比较简洁的答案呢?同时记一下超慢速刷题过半以鼓励自己求一道题的解答
新鲜出炉的amazon面经-phone&onsiteAmazon面经
相关话题的讨论汇总
话题: treenode话题: null话题: return话题: false话题: root