LeetCode(每日一题)-101.对称二叉树

た入场券 2023-10-04 11:26 59阅读 0赞

【题目描述】  
给定一个二叉树，检查它是否是镜像对称的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw_size_16_color_FFFFFF_t_70]  
你可以运用递归和迭代两种方法解决这个问题吗？

解题思路：可以用BFS的思路去解此题，只不过几点注意点:

*  如果子节点为空也存入队列中
 *  入栈的两个节点的位置要是对此的  
    图解：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw_size_16_color_FFFFFF_t_70 1]  
    AC代码（递归）：

public boolean isSymmetric(TreeNode root) {
        
            
            if (root == null)
                return true;
            return CMP(root.left,root.right);
        }
        boolean CMP(TreeNode node1,TreeNode node2){
        
            if(node1 == null&&node2 == null)
                return true;
            if (node1 == null || node2 == null || node1.val != node2.val) {
        
                return false;
            }
            return CMP(node1.left,node2.right)&&CMP(node1.right,node2.left);
        }

AC代码（迭代）

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210421093157121.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210421093806190.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw,size_16,color_FFFFFF,t_70