使用非递归的二叉树遍历实现。
#include<iostream>
using namespace std;
const int maxn=10000;/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
//头节点为空
if(pRoot==NULL)return true;
//定义变量
int top=-1;
TreeNode*pl[maxn],*pr[maxn],*p_l,*p_r;
//初始化栈
top++;pl[top]=pr[top]=pRoot;
//左右序遍历
while(top!=-1)
{
//头节点出栈
p_l=pl[top];p_r=pr[top];top--;
//判断是否对称
if(p_l->val!=p_r->val)return false;
bool bpll=p_l->left==NULL,bplr=p_l->right==NULL;
bool bprl=p_r->left==NULL,bprr=p_r->right==NULL;
if((bpll^bprr)||(bplr^bprl))break;
//将子节点入栈
if(p_l->left!=NULL)
{
top++;
pl[top]=p_l->left;
pr[top]=p_r->right;
}
if(p_l->right!=NULL)
{
top++;
pl[top]=p_l->right;
pr[top]=p_r->left;
}
}
return top==-1;
}
};
经过数十次的提交最后终于过了
第一次找出没有考虑这个if(pRoot==NULL)return true;
提交多次，会想以前写过的遍历算法，递归和非递归都是一样的思路，没有什么漏洞
怀疑栈定义的问题，将maxn改为1000没有用，又改成1e6还是没有用
看了一眼老师和其它同学的提交记录都是使用递归的方法，开始就是怀疑栈溢出，但是使用了数组栈还是溢出应该不可能
整理了一下思路，有看是整理了一下代码
第二次找出判断出错
bool bpll=p_l->left==NULL,bplr=p_l->right==NULL;
bool bprl=p_r->left==NULL,bprr=p_r->right==NULL;
if((bpll^bprr)||(bplr^bprl))break;
还是不行，继续往下找，发现入栈时，判断是这样写的if(p_l!=NULL)and if(p_l!=NULL)
改了过来，过了10%
开始肯定了自己的逻辑，找了一下代码，没错
第三次找出题意的对称不仅仅是形状上的对称，数值上也要对称相等，加上了if(p_l->val!=p_r->val)return false;
然后就过了。
思路：形状上的对称只要，同时先序遍历后序遍历，如果同时存在相同的子节点就对称，数值就在判断子节点的时候，判断一下数值就行。