来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree/

描述

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

说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

题解

递归法

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public boolean isSymmetric(TreeNode root) {
  12.         return isMirror(root, root);
  13.     }
  15.     public boolean isMirror(TreeNode t1, TreeNode t2) {
  16.         if (t1 == null && t2 == null) return true;
  17.         if (t1 == null || t2 == null) return false;
  18.         return (t1.val == t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
  19.     }
  20. }

复杂度分析

  • 时间复杂度：101. 对称二叉树(Symmetric Tree) - 图1，因为我们遍历整个输入树一次，所以总的运行时间为101. 对称二叉树(Symmetric Tree) - 图2，其中101. 对称二叉树(Symmetric Tree) - 图3是树中结点的总数。

  • 空间复杂度：递归调用的次数受树的高度限制。在最糟糕情况下，树是线性的，其高度为101. 对称二叉树(Symmetric Tree) - 图4。因此，在最糟糕的情况下，由栈上的递归调用造成的空间复杂度为101. 对称二叉树(Symmetric Tree) - 图5。

    迭代法

    1. /**
    2. * Definition for a binary tree node.
    3. * public class TreeNode {
    4. *     int val;
    5. *     TreeNode left;
    6. *     TreeNode right;
    7. *     TreeNode(int x) { val = x; }
    8. * }
    9. */
    10. class Solution {
    11.   public boolean isSymmetric(TreeNode root) {
    12.       Queue<TreeNode> queue = new LinkedList<>();
    13.       queue.add(root);
    14.       queue.add(root);
    15.       while (!queue.isEmpty()) {
    16.           TreeNode t1 = queue.poll();
    17.           TreeNode t2 = queue.poll();
    18.           if (t1 == null && t2 == null) {
    19.               continue;
    20.           }
    21.           if (t1 == null || t2 == null) {
    22.               return false;
    23.           }
    24.           if (t1.val != t2.val) {
    25.               return false;
    26.           }
    27.           queue.add(t1.left);
    28.           queue.add(t2.right);
    29.           queue.add(t1.right);
    30.           queue.add(t2.left);
    31.       }
    33.       return true;
    34.   }
    35. }

    复杂度分析

  • 时间复杂度：101. 对称二叉树(Symmetric Tree) - 图6，因为我们遍历整个输入树一次，所以总的运行时间为101. 对称二叉树(Symmetric Tree) - 图7，其中101. 对称二叉树(Symmetric Tree) - 图8是树中结点的总数。

  • 空间复杂度：搜索队列需要额外的空间。在最糟糕情况下，我们不得不向队列中插入101. 对称二叉树(Symmetric Tree) - 图9个结点。因此，空间复杂度为101. 对称二叉树(Symmetric Tree) - 图10。