【原】对称二叉树

问题描述

来源：LeetCode第101题

难度：简单

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]

输出：true

输入：root = [1,2,2,null,3,null,3]

输出：false

提示：

• 树中节点数目在范围 [1, 1000] 内

• -100 <= Node.val <= 100

视频讲解

代码部分

解法一

public boolean isSymmetric(TreeNode root) {
    return helper(root.left, root.right);
}

private boolean helper(TreeNode left, TreeNode right) {
    if (left == null && right == null)
        return true;
    // 如果左子树和右子树一个为空一个不为空，直接返回false
    if (left == null || right == null)
        return false;
    if (left.val != right.val)
        return false;
    // 继续递归子节点
    return helper(left.left, right.right)
            && helper(left.right, right.left);
}

解法二

public boolean isSymmetric(TreeNode root) {
    // 队列
    Queue<TreeNode> queue = new LinkedList<>();
    // 把根节点的左子树和右子树都加入到队列中
    queue.offer(root.left);
    queue.offer(root.right);
    while (!queue.isEmpty()) {
        // 每次出队两个，然后比较
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();

        if (left == null && right == null)
            continue;
        // 如果左子树和右子树一个为空一个不为空，直接返回false
        if (left == null || right == null)
            return false;
        if (left.val != right.val)
            return false;

        // 把子节点加入到队列中，注意加入的顺序
        queue.offer(left.left);
        queue.offer(right.right);

        queue.offer(left.right);
        queue.offer(right.left);
    }
    return true;
}