题解 | #对称的二叉树#

package com.iwen.Sword1;

import com.iwen.小码哥第三季.common.TreeNode;

import java.util.LinkedList;

/**
 * @ClassName 对称的二叉树
 * @Description TODO
 * @Author iwen
 * @Date 2023/6/12 14:19
 * @Version 1.0
 **/
public class 对称的二叉树 {

    /**
     * 给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
     * 方式一：递归，主要是使⽤递归，先判断根节点是否为空，不为空则判断左右⼦树是不是对称。
     * 如果左右⼦树都为空，则返回true，如果有⼀个为空，则返回false，如果两个都不为空的时候，除了对⽐左右两个节点的值，还需要递归，
     * 对⽐左⼦树的左⼦树和右⼦树的右⼦树是否相等，左⼦树的右⼦树和右⼦树的左⼦树是否相等。
     *
     * 方式二：另外⼀种，⾮递归的做法，是借助两个队列，按照层次，⼀个是按照从左到右添加元素，另外⼀个队列是按照从右到左添加元素，挨个取出来，进⾏对⽐，
     * 不等则说明不对称，如果相等，则再把其左右⼦树分别按照不同的顺序添加到队列中。
     * */
    public boolean isSymmetrical(TreeNode pRoot) {
        // 判断根节点是否为空，如果不为空则判断左右⼦树
        return pRoot==null || jude(pRoot.left, pRoot.right);
    }
    boolean jude(TreeNode left, TreeNode right) {
        // 如果左右两个都为空，则对称
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            // 如果左右两个有⼀个为空，那么就不对称
            return false;
        }
        // 都不为空的情况，需要判断两个的值，是不是相等
        if (left.val != right.val) {
            return false;
        } else {
            // 递归判断，左⼦树的左⼦树和右⼦树的右⼦树，左⼦树的右⼦树和右⼦树的左⼦树
            return jude(left.left, right.right) && jude(left.right,right.left);
        }
    }


    boolean isSymmetrical2(TreeNode pRoot){
        if (pRoot == null) return true;
        LinkedList<TreeNode> leftNodes = new LinkedList<>();
        LinkedList<TreeNode> rightNodes = new LinkedList<>();
        leftNodes.add(pRoot.left);
        rightNodes.add(pRoot.right);
        while (!leftNodes.isEmpty() && !rightNodes.isEmpty()) {
            TreeNode leftNode = leftNodes.poll();
            TreeNode rightNode = rightNodes.poll();
            if (leftNode == null && rightNode == null)
                continue;
            if (leftNode == null || rightNode == null)
                return false;
            // 取出来对⽐
            if (leftNode.val != rightNode.val)
                return false;
            // 从左往右添加节点
            leftNodes.add(leftNode.left);
            leftNodes.add(leftNode.right);
            // 从右往左添加节点
            rightNodes.add(rightNode.right);
            rightNodes.add(rightNode.left);
        }
        return leftNodes.isEmpty() && rightNodes.isEmpty();
    }
}

解题思想：

方式一：递归

方式二：借助队列