跳至主要內容

101. 对称二叉树


101. 对称二叉树

🟢   🔖  深度优先搜索 广度优先搜索 二叉树  🔗 力扣open in new window LeetCodeopen in new window

题目

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]

Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]

Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

题目大意

给你一个二叉树的根节点 root , 检查它是否轴对称。

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

解题思路

思路一:递归

二叉树轴对称需要满足:

  • 根节点的左子节点和右子节点对称相等
  • 左子节点的左子节点与右子节点的右子节点对称相等
  • 左子节点的右子节点与右子节点的左子节点对称相等

递归地去判断每一层是否满足以上三个条件。


思路二:迭代

使用队列来对比左子树和右子树上每一个对称的节点对。


思路三:翻转二叉树

这道题是第 226 题 翻转二叉树第 100 题 判断两颗树是否完全相等的综合题,可以将根节点的左子树翻转,然后再和根节点的右子树进行比较,是否完全相等。

代码

递归
var isSymmetric = function (root) {
	if (root == null) return true;
	const isMirror = (left, right) => {
		if (!left && !right) return true;
		if (!left || !right) return false;
		return (
			left.val == right.val &&
			isMirror(left.left, right.right) &&
			isMirror(left.right, right.left)
		);
	};
	return isMirror(root.left, root.right);
};