Leetcode101.对称二叉树

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

示例 1：

symtree1

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

示例 2：

symtree2

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

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100
1
2
3
4
5
   2         2
   / \       / \
  3   4     4   3
 / \ / \   / \ / \
8  7 6  5 5  6 7  8

终止条件：

left 和 right 不等，或者 left 和 right 都为空
递归的比较 left，left 和 right.right，递归比较 left，right 和 right.left

解法1：递归

使用递归比较简单直接：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    public boolean check(TreeNode left,TreeNode right){
        if (left == null && right == null)return true;
        if (left == null || right == null)return false;
        return left.val == right.val && check(left.left,right.right) && check(left.right,right.left);

    }
}

解法2：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null))return true;
        
        LinkedList <TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root.left);
        queue.add(root.right);

        while (queue.size()>0){
            TreeNode left = queue.removeFirst();
            TreeNode right= queue.removeFirst();

            if(left==null && right==null)continue;
            if(left==null || right == null)return false;
            if(left.val != right.val)return false;

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

    }
}