题解 | #判断二叉树是否对称#

非递归思路

对于前序遍历：根节点=》左子树=》右子树
若需要判断对称性，那么可以修改前序遍历的方式，即：
①根节点=》左子树=》右子树
②根节点=》右子树=》左子树
①和②采取非递归的方式同步推进，研究中间每个节点是否对称

对于如何同步推进，可以采取以其中一个的前序遍历为主推进，研究另一个是否能同步对称推进

代码实现

 bool isSymmetric(TreeNode* root) {
        // write code here

        stack<TreeNode*> stk1,stk2;//栈
        TreeNode* p1=root;
        TreeNode* p2=root;//两个指针

        while(p1!=NULL || stk1.empty()==false)  //主框架按照前序遍历进行
        {

            if(p1!=NULL) 
            {
                if(p2==NULL)  //发生了不对称
                    return false;
                //开始研究两个对称点是否相等
                if(p1->val!=p2->val)
                    return false;
                //将访问到的存入stack中
                stk1.push(p1);
                stk2.push(p2);
                p1=p1->left;  //一个往左边下降
                p2=p2->right;  //一个往右边下降


            }
            else
            {
                if(p2!=NULL)
                    return false;  //发生了不对称性
                p1=stk1.top()->right;//p1转移到没有访问的右边
                if(stk2.empty()==true)
                    return false;  //stk2已经访问完
                p2=stk2.top()->left;//p2转移到没有访问的左边
                stk1.pop();
                stk2.pop();


            }


        }

        return true;

    }