题解 | #对称的二叉树#

非递归中序遍历求解

从两个方向进行中序遍历 对比

    TreeNode stack1[]=new TreeNode[500];
    int top1=-1;
    TreeNode stack2[]=new TreeNode[500];
    int top2=-1;

    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot!=null)
        {
            TreeNode p=pRoot;//从正常中序的方向遍历（左 根 右）
            TreeNode m=pRoot;//从反向中序的方向遍历（右 根 左）
            while(top1!=-1 || p!=null)//我们以正常中序能遍历到的节点为准
            {
                while(p!=null)
                {
                    //正常中序往左走 入栈
                    //反向的往右走 入栈
                    stack1[++top1]=p;
                    stack2[++top2]=m;
                    p=p.left;
                    m=m.right;
                    if(p!=null && m==null) return false;
                }
                //走到头
                if(top1!=-1)//拿出比较，选取右/左孩子 继续
                {
                    p=stack1[top1--];
                    m=stack2[top2--];
                    if(p.val!=m.val) return false;
                    /** TODO：我们是以正常中序能遍历到的节点为准，没有考虑反向的，
                    *   如果这时m还没走到头，可以在这判断一下
                    *   但是我没写，本题可以ac
                    */
                    p=p.right;
                    m=m.left;
                    if(p!=null && m==null) return false;
                }
            }
        }

        return true;
    }