leetcode：对称二叉树

桃扇骨 2023-03-06 03:50 100阅读 0赞

#### [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

看题第一想法就是一层一层的来，判断每一层是不是对称的，想着用队列`BFS`做，空的子树按照null来比较，下一层进队的时候按照`front.left`与`rear.right`一组，`front.rignt`与`rear.left`一组存（本来想按照正常的顺序存，使用双端队列，发现双端队列不是取的时候前后取，而是存的时候顺序不一样。）前后对称进行比较，不相等直接返回false.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 1]

好家伙，太慢了。迭代太慢的话尝试尝试看看递归能不能来写，根据迭代的判断条件直接来写递归。

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if(root == null){
        
                return true;
            }
            return helper(root.left,root.right);
        }
        public boolean helper(TreeNode front,TreeNode rear){
        
            if(front == null && rear == null ){
        
                return true;
            }
            if(front == null || rear == null || front.val != rear.val){
        
                return false;
            }
            return helper(front.left,rear.right) && helper(front.right,rear.left);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 2]

和迭代的判断条件没有任何变化，但代码上更简短，效率也更高。递归真香。

[101.]: https://leetcode-cn.com/problems/symmetric-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: /images/20230208/cbb8f8d90573462b937ba536549e8d7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230208/25e0999fbf894da1aeeb17afd8dc2031.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230208/3afe6f6c3f804dada4b613297f12f72b.png