29_对称的二叉树

要求：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如：二叉树 [1,2,2,3,4,4,3] 是对称的。但是这个 [1,2,2,null,3,null,3] 则不是镜像对称的。(层次遍历)

思路：
方法一：采用递归，首先根节点以及其左右子树。其次，左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同即可。

二叉树的对称g

// 使用递归
public class L29_isSymmetric {
    // 判断是否是对称二叉树主函数
    public boolean isSymmetric(TreeNode0 root){
        // 判断根节点的值是否为空，没有一个节点的二叉树，也是对称的
        if(root == null){
            return true;
        }
        // 开始进入递归的部分，每次加入两个节点
        return recur(root.left,root.right);
    }
    // 递归部分
    public boolean recur(TreeNode0 left, TreeNode0 right){
        // 如果传入的节点都为空，且这一层的节点都为空，那么这个二叉树是对称的
        if(left == null && right == null){
            return true;
        }
        // 仅有一个节点是不为空，那么这个二叉树一定不对称
        if(left==null||right==null||left.value==right.value){
            return false;
        }
        // 进入递归，左子树的左子树和右子树的右子，左子树的右子树和右子树的左子树组成一队。
        return recur(left.left,right.right) && recur(left.right,right.left);
    }
}

方法二：使用栈来保存成对节点。
1.出栈的时候也是成对的，
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
4.确定入栈顺序，每次入栈都是成对的，如left.left,right.right ; left.rigth,right.left

    public boolean isSymmetrical(TreeNode0 root){
        if(root==null)return true;
        Stack<TreeNode0> stack = new Stack<>();
        stack.add(root.left);
        stack.add(root.right);
        // 当栈为空时跳出循环
        while(!stack.isEmpty()){
            // 成对取出
            TreeNode0 right = stack.pop();
            TreeNode0 left = stack.pop();
            if(right==null&&left==null)return true;
            if(left==null||right==null||left.value==right.value)return false;
            // 成对插入
            stack.add(left.left);
            stack.add(right.right);
            stack.add(left.right);
            stack.add(right.left);
        }
        return true;
    }