LeetCode P101--对称二叉树 递归、迭代

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

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

二叉树结点定义如下：

public class TreeNode {
          
   
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) {
          
    val = x; }
  }

看到对称，我首先考虑到的是遍历然后判断回文，，后来想想这种方法不可取，首先要考虑结点 为 null 的情况，其次要是结点存在 null 那么就会判断不准确。 然后想法就是同时遍历二叉树根节点的左子树和右子树，二叉树是否是镜像对称的取决于 leftTree.left是否等于rightTree.right 且 leftTree.right 是否等于 rightTree.left 那么根据这个想法就可以得到下面的代码

public boolean isSymmetric(TreeNode root) {
          
   
		//如果根节点为空，那么必然是对称
        if (root == null) {
          
   
            return true;
        }
        return isSymmetricCheck(root, root);
    }
    //递归
    private boolean isSymmetricCheck(TreeNode p, TreeNode q) {
          
   
    	//如果左子树和右子树都为空，那么对称
        if (p == null && q==null) {
          
   
            return true;
        }
        //如果只有其中一边对称，那么不可能对称，返回 false
        if (p == null || q == null) {
          
   
            return false;
        }
        //递归继续判断
        return p.val == q.val && isSymmetricCheck(p.left, q.right) && isSymmetricCheck(p.right, q.left);
    }

下面是递归方法的执行用时、内存消耗 如果不想使用递归的形式，那么用迭代也是可以的，想法还是和前面的一样，我们只要建立一个队列，首先把根节点左右结点p、q存进去，每次都从队列中取两个结点，判断是否为 null 和结点值会否相等，然后再把取出来的结点的左右结点按顺序存进队列，由于每次都是取两个结点进行判断，那么存进去的顺序应该为 p.left -> q.right -> p.right -> q.left 具体代码如下：

public boolean isSymmetric(TreeNode root) {
          
   
		//如果根节点为空，那么必然是对称
        if (root == null) {
          
   
            return true;
        }
        return isSymmetricCheck(root, root);
    }
    //迭代
    private boolean isSymmetricCheck(TreeNode p, TreeNode q) {
          
   
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //先存进左右结点（根节点）
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()) {
          
   
			//每次都是取两个结点进行判断
            p = queue.poll();
            q = queue.poll();
            //如果两个结点都是空，那么直接结束本次循环
            if ( p == null && q == null) {
          
   
                continue;
            }
            //如果只有其中一个结点为空或者两个结点对应的值不相等，
            //那么此时必定不能成为镜像对称二叉树，直接返回false
            if ((p == null || q == null) || (p.val != q.val)) {
          
   
                return false;
            }
            //按照上面说的顺序存进结点
            //镜像对称二叉树要 p.left.val = q.right.val
            queue.offer(p.left);
            queue.offer(q.right);
			//同时也要满足 p.right.val = q.left.val
			//所以也同时存进去，以便后面直接判断
            queue.offer(p.right);
            queue.offer(q.left);
        }
        //如果在while循环中没有返回false，
        //那么证明该二叉树满足镜像对称，返回true
        return true;
    }

下面是迭代方法的执行时间、内存消耗 运行结果表明在该题 递归方法 无论在执行时间和内存消耗 都比迭代好一点 即使两种方法的时空复杂度都是O(n)，猜测原因是，递归可以更早结束循环，所以会比迭代略快。