101.对称二叉树

链接：101.对称二叉树
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给定一个二叉树，检查它是否是镜像对称的。

题解 1 - java

• 编辑时间：2020-02-22
• 执行用时：1ms
• 内存消耗：37.7MB
• 编程语言：java
• 解法介绍：遍历。

/**
 * 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;
		Deque<TreeNode> deque = new LinkedList<TreeNode>();
		deque.offer(root.left);
		deque.offer(root.right);
		while (!deque.isEmpty()) {
			TreeNode left = deque.pollFirst();
			TreeNode right = deque.pollLast();
			if (left == null && right == null)
				continue;
			if (left == null || right == null)
				return false;
			if(left.val!=right.val)return false;
			deque.offerFirst(left.right);
			deque.offerFirst(left.left);
			deque.offerLast(right.left);
			deque.offerLast(right.right);
		}
		return true;
	}
}

题解 2 - java

• 编辑时间：2020-02-22
• 执行用时：1ms
• 内存消耗：37.9MB
• 编程语言：java
• 解法介绍：递归。

/**
 * 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;
		if (!inIsSymmetric(root.left, root.right))
			return false;
		return true;
	}
	public boolean inIsSymmetric(TreeNode node1, TreeNode node2) {
		if (node1 == null && node2 == null)
			return true;
		if (node1 == null || node2 == null)
			return false;
		if (node1.val != node2.val)
			return false;
		return inIsSymmetric(node1.left, node2.right) && inIsSymmetric(node1.right, node2.left);
	}
}

题解 3 - typescript

• 编辑时间：2020-02-22
• 执行用时：88ms
• 内存消耗：37MB
• 编程语言：typescript
• 解法介绍：递归。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
var isSymmetric = function (root: TreeNode | null): boolean {
  if (root === null) return true;
  return isSymNode(root.left, root.right);
  function isSymNode(node1: TreeNode | null, node2: TreeNode | null): boolean {
    if (node1 === null && node2 === null) return true;
    if (node1 === null || node2 === null || node1.val !== node2.val) return false;
    return isSymNode(node1.left, node2.right) && isSymNode(node1.right, node2.left);
  }
};

题解 4 - c

• 编辑时间：2021-11-27
• 执行用时：4ms
• 内存消耗：6.5MB
• 编程语言：c
• 解法介绍：递归。

// 校验两个树是否镜像
bool _isSymmetric(struct TreeNode *node1, struct TreeNode *node2){
    // 都为NULL就是
    if (!node1 && !node2) return 1;
    // 其中一个为NULL或者值不等就不是
    if (!node1 || !node2 || node1->val != node2->val) return 0;
    // 否则递归判断：node1的左和node2的右是否镜像、node1的右和node2的左是否镜像
    return _isSymmetric(node1->left, node2->right) && _isSymmetric(node1->right, node2->left);
}
bool isSymmetric(struct TreeNode* root){
    return _isSymmetric(root->left, root->right);
}