LeetCode 101. 对称二叉树

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 101. 对称二叉树

思路分析

递归

参考代码

// 判断两个节点是否镜像对称
func isMirror(left *TreeNode, right *TreeNode) bool {
	if left == nil && right == nil {
		return true
	}
	if left == nil || right == nil {
		return false
	}
	if left.Val != right.Val {
		return false
	}
	// 递归判断
	return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isMirror(root.Left, root.Right)
}

// 判断是否是对称树
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}

	// 判断两个子树是否镜像
	var isMirror func(p *TreeNode, q *TreeNode) bool
	isMirror = func(p *TreeNode, q *TreeNode) bool {
		// 都为空说明对称
		if p == nil && q == nil {
			return true
		}
		// 有一个为空说明不对称
		if p == nil || q == nil {
			return false
		}
		// 当前节点值不同，不对称
		if p.Val != q.Val {
			return false
		}
		// 递归判断 左-右 和 右-左
		return isMirror(p.Left, q.Right) && isMirror(p.Right, q.Left)
	}

	return isMirror(root.Left, root.Right)
}

时间复杂度：O (n)，其中 n 是节点的数量。

空间复杂度：O (h)，其中 h 是树的高度。

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}

	queue := []*TreeNode{root.Left, root.Right}

	for len(queue) > 0 {
		t1 := queue[0]
		t2 := queue[1]
		queue = queue[2:]

		if t1 == nil && t2 == nil {
			continue
		}
		if t1 == nil || t2 == nil || t1.Val != t2.Val {
			return false
		}

		queue = append(queue, t1.Left, t2.Right, t1.Right, t2.Left)
	}

	return true
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/52259577