101. 对称二叉树（简单）

电玩女神 2022-09-10 01:24 131阅读 0赞

Leetcode链接：[101. 对称二叉树][101.]

### 题目描述 ###

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 `[1,2,2,3,4,4,3]` 是对称的。

1
       / \
      2   2
     / \ / \
    3  4 4  3

但是下面这个 `[1,2,2,null,3,null,3]` 则不是镜像对称的:

1
       / \
      2   2
       \   \
       3    3

**进阶**：

你可以运用`递归`和`迭代`两种方法解决这个问题吗？

### 源码 ###

##### 递归解法 #####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            return helper(root, root);
        }
    
        public boolean helper(TreeNode node1, TreeNode node2){
        
            if(node1 == null && node2 == null) return true;
            if(node1 == null || node2 == null) return false;
    
            return node1.val == node2.val && helper(node1.left, node2.right) && helper(node1.right, node2.left);
        }
    }

##### 迭代解法 #####

使用队列模拟层次遍历的效果

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            return check(root, root);
        }
    
        public boolean check(TreeNode p, TreeNode q){
        
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(p);
            queue.offer(q);
    
            while(!queue.isEmpty()){
        
                p = queue.poll();
                q = queue.poll();
    
                if(p == null && q == null) continue;
                if(p == null || q == null || p.val != q.val) return false;
    
                queue.offer(p.left);
                queue.offer(q.right);
    
                queue.offer(p.right);
                queue.offer(q.left);
            }
    
            return true;
        }
    }

[101.]: https://leetcode-cn.com/problems/symmetric-tree/