题目地址(101. 对称二叉树)

https://leetcode-cn.com/problems/symmetric-tree/

题目描述

  1. 给定一个二叉树，检查它是否是镜像对称的。
  5. 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
  7.     1
  8.    / \
  9.   2   2
  10.  / \ / \
  11. 3  4 4  3
  16. 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
  18.     1
  19.    / \
  20.   2   2
  21.    \   \
  22.    3    3
  27. 进阶：
  29. 你可以运用递归和迭代两种方法解决这个问题吗？

前置知识


公司

  • 暂无

思路

要比较外侧和内侧节点的不同 需要判断节点为空或者不为空的情况
节点为空的情况有

  • 左节点为空，右节点不为空，不对称，return false
  • 左不为空，右为空，不对称 return false
  • 左右都为空，对称，返回true

把这些都排除了 就只剩下不为空的了 然后再判断量变数字是否相等 就o了

递归法效率高点

关键点


代码

  • 语言支持：Java

Java Code:
递归法

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public boolean isSymmetric(TreeNode root) {
  19.             return compare(root.left, root.right);
  20.         }
  21.         public boolean compare(TreeNode left , TreeNode right){
  22.             //比较节点是否对称 情况1 左空右不空
  23.             if (left == null && right != null) {
  24.                 return false;
  25.             }
  26.             //情况2 左不空右空
  27.             if (left != null && right == null) {
  28.                 return false;
  29.             }
  30.             //情况3 左右都空
  31.             if (left == null && right == null) {
  32.                 return true;
  33.             }
  34.             //比较值是否不相等 这里判断完之后就只剩下相等的情况了
  35.             if (left.val != right.val) {
  36.                 return false;
  37.             }
  38.             //比较外层
  39.             boolean leftT = compare(left.left, right.right);
  40.             //比较内层
  41.             boolean leftR = compare(left.right, right.left);
  42.             return leftT && leftR;
  43.         }
  44.     }

迭代法:

  1. class Solution {
  2.         public boolean isSymmetric(TreeNode root) {
  3.             Queue<TreeNode> queue = new LinkedList<>();
  4.             queue.offer(root.left);
  5.             queue.offer(root.right);
  6.             while (!queue.isEmpty()) {
  7.                 TreeNode left = queue.poll();
  8.                 TreeNode right = queue.poll();
  9.                 if (left == null && right == null) {
  10.                     continue;
  11.                 }
  12.                 if (left == null || right == null || left.val != right.val) {
  13.                     return false;
  14.                 }
  15.                 queue.offer(left.left);
  16.                 queue.offer(right.right);
  17.                 queue.offer(left.right);
  18.                 queue.offer(right.left);
  19.             }
  20.             return true;
  21.         }
  22.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：101. 对称二叉树 2 - 图1#card=math&code=O%28n%29&id=UVPcG)
  • 空间复杂度：101. 对称二叉树 2 - 图2#card=math&code=O%28n%29&id=KCpTT)