package 二叉树.BT;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * https://leetcode-cn.com/problems/symmetric-tree/
 * 
 * @author Huangyujun
 *
 */
public class _101_对称二叉树 {
    /**
     * 作者的思路是：
     * 两块镜子的思维（该过程使用层序遍历~迭代的，使用的数据结构是队列~同时进行添加~ ）：第一个镜子添加进入了左，则第二个镜子添加进入了右 然后第一个镜子添加进入了右，第二个镜子添加进入了左
     * 非常非常的巧妙的一个点是作者通过了一个队列的数据结果实现了一个镜子变成两个镜子的效果 （同时成双添加）
     * 这里使用的数据结构是：队列（特点先进先出），为了进行（“两面镜子”）每一层的遍历的同步对比
     * @author Huangyujun
     *
     */
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            return check(root, root);
        }
        public boolean check(TreeNode u, TreeNode v) {
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(u);
            q.offer(v);
            while (!q.isEmpty()) {
                u = q.poll();
                v = q.poll();
                if (u == null && v == null) {
                    continue;
                }
                if ((u == null || v == null) || (u.val != v.val)) {
                    return false;
                }
                q.offer(u.left);
                q.offer(v.right);
                q.offer(u.right);
                q.offer(v.left);
            }
            return true;
        }
    }
    // 使用递归实现
    class Solution2 {
        public boolean isSymmetric(TreeNode root) {
            return check(root, root);
        }
        public boolean check(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            }
            if (p == null || q == null) {
                return false;
            }
            return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
        }
    }
    // （我写的递归法（思路跟官网差不多，但是细节不到位））
    // 要多看看官网的代码思路，尤其是最后一句：结果：
    // return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return false;
        // 不是null的情况下（左子树是对称的、右子树是对称的，同时左右子树实现对称）
        // 需要两个参数
        return isSymmetric(root, root);
    }
    // 相当于两个树（结点）（方法的参数）
    public boolean isSymmetric(TreeNode root1, TreeNode root2) {
        if (root1.val != root2.val)
            return false;
        // 少了一个条件的判断：
        if (root1 == null || root2 == null)
            return false;
        // 分身实现左边跟右边对比，右边跟左边对比
        boolean leftSymmetric = isSymmetric(root1.left, root2.right); // 同时俩个树的左子树相等
        boolean rightSymmetric = isSymmetric(root1.right, root2.left); // 同时俩个树的左子树相等
        if (leftSymmetric == false || rightSymmetric == false)
            return false;
        return true;
    }
}