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

package suanfa.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;

/**

• 对称二叉树

• 采用递归的方法解决该题。判断二叉树是否为镜像涉及到的是左右两个子树，和根结点没有关系。因此定义函数isSymmetricCore，将两个子树头结点A、B作为传入函数的参数。

• 设置退出情况：

• 如果A、B都为空，说明前面的判断都已经满足要求，因此返回值为true

• 如果A和B中有一个为空，显然不匹配

• 如果A和B都不为空，判断A和B的值是否相等，如果相等，则继续比较A的左子树和B的有子树以及A的右子树和B的左子树；如果不等，则返回false

• 作者：emergence

• 链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/mian-shi-ti-28dui-cheng-de-er-cha-shu-by-dkgp/

• 来源：力扣（LeetCode）

• 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• /
  public class Symmetric {

  public static void main(String[] args) {

    TreeNode leftR = new TreeNode();
    leftR.val = 3;
  
    TreeNode rightL = new TreeNode();
    rightL.val = 3;

    TreeNode left = new TreeNode();
    left.val = 2;
    left.right = leftR;

    TreeNode right = new TreeNode();
    right.val = 2;
    right.left = rightL;


    TreeNode root = new TreeNode();
    root.val = 1;
    root.left = left;
    root.right = right;

    System.out.println(isSymmetric(root));
}


public static boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return compare(root.left, root.right);
}


public static Boolean compare(TreeNode left, TreeNode right) {

    if (left == null && right == null) {
        return Boolean.TRUE;
    }
    if (left != null && right == null) {
        return Boolean.FALSE;
    }

    if (left == null && right != null) {
        return Boolean.FALSE;
    }

    if (left.val != right.val) {
        return Boolean.FALSE;
    }

    if (left.right != null && right.left != null && left.right.val != right.left.val) {
        return Boolean.FALSE;
    }

    if (left.left != null && right.right != null && left.left.val != right.right.val) {
        return Boolean.FALSE;
    }

    return compare(left.left, right.right) && compare(left.right, right.left);
}

/**
 * 二叉树的层序遍历 依赖queue实现
 *
 * @param root
 * @return
 */
public static boolean levelOrder(TreeNode root) {
    if (root == null) {
        return Boolean.TRUE;
    }
    List<List<Integer>> allList = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedBlockingDeque<>();
    queue.add(root);

    while (!queue.isEmpty()) {

        List<Integer> subList = new ArrayList<>();

        int currentLevelSize = queue.size();
        if (allList.size() >= 1 && currentLevelSize % 2 != 0) {
            return Boolean.FALSE;
        }

        for (int i = 1; i <= currentLevelSize; i++) {

            TreeNode tmpNode = queue.poll();
            subList.add(tmpNode.val);

            if (tmpNode.left != null) {
                queue.offer(tmpNode.left);
            }

            if (tmpNode.right != null) {
                queue.offer(tmpNode.right);
            }

        }
        int left = 0;
        int right = subList.size() - 1;

        while (left <= right) {
            if (!subList.get(left).equals(subList.get(right))) {
                return Boolean.FALSE;
            }
            left++;
            right--;
        }
        allList.add(subList);
    }

    return Boolean.TRUE;
}


static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

}