k*******a
发帖数: 433 | 1 我只做出来了recursive的方法，请问迭代的方法怎么做？
谢谢！ |
c*******e
发帖数: 621 | 2 所有recursive的题都能用stack做 你要熟悉啊
tripadvisor考到过
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root==NULL)return true;
if(root->left==NULL||root->right==NULL){
if(root->left==NULL&&root->right==NULL)return true;
return false;
}
stack s1,s2;
s1.push(root->left);
s2.push(root->right);
while(!s1.empty()&&!s2.empty()){
TreeNode *n1=s1.top(),*n2=s2.top();
s1.pop();s2.pop();
if(n1->val!=n2->val)return false;
if(n1->left!=NULL&&n2->right!=NULL){
s1.push(n1->left);
s2.push(n2->right);
}
else if(n1->left!=NULL||n2->right!=NULL)
return false;
if(n1->right!=NULL&&n2->left!=NULL){
s1.push(n1->right);
s2.push(n2->left);
}
else if(n1->right!=NULL||n2->left!=NULL)
return false;
}
return true;
}
}; |
k*******a
发帖数: 433 | 3 你好牛！
谢了！
【在 c*******e 的大作中提到】
: 所有recursive的题都能用stack做 你要熟悉啊
: tripadvisor考到过
: /**
: * Definition for binary tree
: * struct TreeNode {
: * int val;
: * TreeNode *left;
: * TreeNode *right;
: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
: * };
|
j*****0
发帖数: 160 | 4 我用的bst，思想就是左子树放一个队列右子树以反方向放一个队列，然后从队列中抽
出脑袋的时候比比。
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue left_q = new LinkedList();
Queue right_q = new LinkedList();
left_q.offer(root.left);
right_q.offer(root.right);
while (!left_q.isEmpty() && !right_q.isEmpty()) {
TreeNode left = left_q.poll();
TreeNode right = right_q.poll();
if (left == null && right == null) {
continue;
} else if (left == null || right == null) {
return false;
} else {
if (left.val != right.val) {
return false;
}
left_q.offer(left.left);
left_q.offer(left.right);
right_q.offer(right.right);
right_q.offer(right.left);
}
}
return true;
} |
k*******a
发帖数: 433 | 5 你们两个都很强大！
前者用的c++,不知道后面那个用的什么语言啊？ |
j*****0
发帖数: 160 | 6 java，我把前面class去掉了
【在 k*******a 的大作中提到】
: 你们两个都很强大！
: 前者用的c++,不知道后面那个用的什么语言啊？
|
I**********s
发帖数: 441 | 7 也用stack. 简洁一些，也能过。
bool isSymmetric3(TreeNode * root) {
if (! root) return true;
stack s1, s2;
s1.push(root->left);
s2.push(root->right);
while(! s1.empty() && ! s2.empty()) {
TreeNode * n1 = s1.top(); s1.pop();
TreeNode * n2 = s2.top(); s2.pop();
if (!n1 && !n2) continue;
if (!n1 || !n2 || n1->val != n2->val) return false;
s1.push(n1->left);
s1.push(n1->right);
s2.push(n2->right);
s2.push(n2->left);
}
return true;
} |
I**********s
发帖数: 441 | 8 完全相同的结构，改用queue, 也能过：
bool isSymmetric(TreeNode * root) {
if (! root) return true;
queue s1, s2;
s1.push(root->left);
s2.push(root->right);
while(! s1.empty() && ! s2.empty()) {
TreeNode * n1 = s1.front(); s1.pop();
TreeNode * n2 = s2.front(); s2.pop();
if (!n1 && !n2) continue;
if (!n1 || !n2 || n1->val != n2->val) return false;
s1.push(n1->left);
s1.push(n1->right);
s2.push(n2->right);
s2.push(n2->left);
}
return true;
} |
