101. 对称二叉树

这题算简单？？？我觉得中等不过分

迭代法，BFS

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        //空树或者只有一个root
        if(root == null || (root.left == null && root.right == null)) return true;
        //判断root左右节点是否存在至少一个，如果存在，则如果两个都存在且val相等继续，其他情况返回false，相等则继续。
        if(root.left != null || root.right != null){
            if(root.left != null && root.right != null && root.left.val == root.right.val) ;
            else return false;
        }
        queue.add(root.right);
        queue.add(root.left);
        //栈两个两个放，两个两个取
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                TreeNode left = queue.poll();
                TreeNode right = queue.poll();
                //处理左.左孩子和右.右孩子
                if(left.left != null || right.right != null){
                    if(left.left != null && right.right != null && left.left.val ==  right.right.val) {
                        queue.add(right.right);
                        queue.add(left.left);
                    } else return false;
                }
                //处理左.右孩子和右.左孩子
                if(left.right != null || right.left != null){
                    if(left.right != null && right.left != null && left.right.val == right.left.val){
                        queue.add(right.left);
                        queue.add(left.right);
                    } else return false;
                }
                size--;
                size--;
            }
        }
        return true;
    }
}

给个改进版

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        //空树或者只有一个root
        if(root == null || (root.left == null && root.right == null)) return true;
        queue.add(root.right);
        queue.add(root.left);
        //栈两个两个放，两个两个取
        while(!queue.isEmpty()){
        
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;

            queue.add(right.right);
            queue.add(left.left);

            queue.add(right.left);
            queue.add(left.right);

        }
        return true;
    }
}

循环内直接处理当前节点自身的逻辑，而不是处理它的子节点逻辑，简洁很多

我自己用递归做出来了！，我TM真是个秀儿

class Solution {
    boolean res = true;
    public boolean isSymmetric(TreeNode root) {
        //空树或者只有一个root
        if(root == null || (root.left == null && root.right == null)) return true;
        return checkfun(root.left,root.right);
    }
    public boolean checkfun(TreeNode left,TreeNode right) {
        if(left == null && right == null) return res;
        if(left == null || right == null) return res && false;
        if(left.val != right.val) return res && false;
        return checkfun(left.left,right.right) && checkfun(left.right,right.left);
    }
}

md官方答案比我还简略，生气= =

class Solution {
    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);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/symmetric-tree/solution/dui-cheng-er-cha-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。