力扣LeetCode 101：对称二叉树（递归&等价替换迭代）

偏执的太偏执、 2023-02-14 06:58 12阅读 0赞

题目：

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

> 例如，二叉树 \[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

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

既然题目已经说了用迭代和递归两种方法，那就用这两种方法 8

### 一、递归 ###

递归是比较容易想到的。

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

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

在这个树里面，左子树的val = 右子树的val；  
**左.右的 val = 右.左的 val；左.左的val = 右.右的 val**

可以想到，在不为空的前提下  
所有**左右左右右左…………的val 都应该 = 右左右左左…………的val**，就是镜像对称了；  
如果为空，那得 比较双方同时 为空，这样也是镜像对称；  
否则就不对称了。

递归操作的过程，就是一边取右子树，一边取左子树，保证镜面。然后就能写出代码：

/**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if(root==null){
        
                return true;
            }
            TreeNode left=root.left;
            TreeNode right=root.right;
            return isSame(left,right);
        }
        
        /*
        *	递归的核心方法，传入需要比较的两个节点，在方法里比较他们的val，
        *	然后递归的对他们的 镜像 子节点进行比较
        */
        public boolean isSame(TreeNode left,TreeNode right){
        
            if(left!=null&&right!=null){
        
                //1.如果不为空，判断值。
                //同时递归左右右左，左左右右的判断
                return (left.val==right.val) && ( isSame(left.left,right.right))
                    && (isSame(left.right,right.left)) ;
            }else if(left==null&& right==null){
        
                return true;//2.如果空，那得同时为空
            }else{
        
                return false;
            }
        }
    }

### 二、迭代 ###

递归和迭代法的替换，一般的做法就是维护一个队列。

既然我们比较完当前的 左 和 右 之后，需要对 左.左 ，右.右 和 左.右，右.左 两对节点进行继续比较，那就在把左和右出队之后，把另外两对入队。这样  
就能达到一样的效果。

Queue的实现类有很多。可以看一下这篇博客的笔记：  
https://blog.csdn.net/u010871004/article/details/52604171

用迭代替代递归的代码如下：

/**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
    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 left=queue.poll();
                TreeNode right=queue.poll();
                
                if(left==null&&right==null){
        
                    continue;
                }
                if(left==null || right==null || left.val != right.val){
        
                    return false;
                }
                //下面offer的顺序需要注意，一次进去的两个，需要能比较的
                queue.offer(left.right);
                queue.offer(right.left);
    
                queue.offer(left.left);
                queue.offer(right.right);
            }
            return true;
        }
    }