对称二叉树
递归法
算法思想: DFS
先
dfs
传入根节点的左右俩个节点
若俩个节点都不存在,则返回true
若仅有一个节点存在,或俩个节点存在但值不相等,则返回false
这时这俩个节点值一定相等,只需返回dfs
左的左和右的右&&dfs
左的右和右的左
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return dfs(root->left,root->right);
}
bool dfs(TreeNode* l,TreeNode* r){
if(!l&&!r) return true;
if((!l&&r)||(l&&!r)||(l->val!=r->val)) return false;
return dfs(l->right,r->left)&&dfs(l->left,r->right);
}
};
迭代法
思路一:(双栈,依次入栈)
class Solution {
public:
bool isSymmetric(TreeNode* root) {
stack<TreeNode*> l;
stack<TreeNode*> r;
l.push(root->left);
r.push(root->right);
while(l.size()&&r.size()){
auto p=l.top();l.pop();
auto q=r.top();r.pop();
if(!p&&!q) continue;
if((q&&!p)||(!q&&p)||p->val!=q->val) return false;
if(p&&q){
l.push(p->left);l.push(p->right);
r.push(q->right);r.push(q->left);
}
}
return true;
}
};
思路二:(双栈,一次性循环入栈)
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==NULL) return true;
auto l=root->left,r=root->right;
stack<TreeNode*> st1,st2;
while(l||r||st1.size()||st2.size()){
while(l&&r){
st1.push(l),l=l->left;
st2.push(r),r=r->right;
}
if(l||r) return false;
l=st1.top(),st1.pop();
r=st2.top(),st2.pop();
if(l->val!=r->val) return false;
l=l->right,r=r->left;
}
return true;
}
};