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

package org.example.test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class SymmetricTest {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(2);
        node1.left = node2;
        node1.right = node3;
        System.out.println(isSymmetric(node1));
    }

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

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 迭代算法，BFS
     *
     * @param root
     * @return
     */
    public static boolean isSymmetric(TreeNode root) {
        // write code here
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        Stack<Integer> stack = new Stack<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            if (size % 2 != 0 && queue.peek() != root) {
                return false;
            }
            int half = size / 2;
            while (size > 0) {
                TreeNode node = queue.poll();
                if (size > half) {
                    stack.push(node == null ? 1 : node.val);
                } else {
                    int tmp = node == null ? 1 : node.val;
                    if (stack.pop() != tmp) {
                        return false;
                    }
                }
                size--;
                if (node == null) {
                    continue;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.left == null && node.right != null) {
                    queue.offer(null);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null && node.right == null) {
                    queue.offer(null);
                }
            }
        }
        return true;
    }

/**
     * 递归算法
     *
     * @param root
     * @return
     */
    public static boolean isSymmetric1(TreeNode root) {
        if (root == null) {
            return true;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        return symmetric(left, right);
    }

    private static boolean symmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null) {
            return false;
        }
        if (right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        boolean x = symmetric(left.left, right.right);
        boolean y = symmetric(left.right, right.left);
        return x && y;
    }
}