LeetCode.101. 对称二叉树

101. 对称二叉树

难度：easy

 两种方法：

第一种：递归方法

// 递归方法
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return compare(root.left, root.right);
    }
 
    public boolean compare(TreeNode leftNode, TreeNode rightNode) {
        // 左节点和右节点都为空：true
        // 左右节点只有一个为空，false
        // 左右节点都不为空，但左右节点得值不相等
        if (leftNode == null && rightNode == null) {
            return true;
        } else if ((leftNode != null && rightNode == null) || (leftNode == null && rightNode != null)) {
            return false;
        } else if (leftNode.val != rightNode.val) {
            return false;
        }
        // 比较左右节点得内外侧子节点
        boolean outSideCompare = compare(leftNode.left, rightNode.right);
        boolean inSideCompare = compare(leftNode.right, rightNode.left);
        return outSideCompare && inSideCompare;
    }
}

第二种方法：通过队列或者栈来实现

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
 
        Queue queue = new LinkedList();
        queue.offer(root.left);
        queue.offer(root.right);
 
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
 
            if (node1 == null && node2 == null) {
                continue;
            } else if ((node1 == null && node2 != null) || (node1 != null && node2 == null)) {
                return false;
            } else if (node1.val != node2.val) {
                return false;
            }
 
            queue.offer(node1.left);
            queue.offer(node2.right);
            queue.offer(node1.right);
            queue.offer(node2.left);
        }
        return true;
    }
}

推免后做得第一道题，纪念一下哈哈。