LeetCode 剑指 Offer 28. 对称的二叉树

Categories:

题目描述
思路分析
1. 解法一：递归比较（推荐）
相似题目

题目描述

✅ 剑指 Offer 28. 对称的二叉树

思路分析

解法一：递归比较（推荐）

核心思路：

判断两棵树是否镜像：根值相等，左子树与右子树互为镜像。

对原树调用 isMirror(root, root)。

递归基：同为空为真，一空一非空为假。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树高，递归栈空间。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    private boolean isMirror(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        if (a.val != b.val) {
            return false;
        }

        return isMirror(a.left, b.right) && isMirror(a.right, b.left);
    }
}

func isSymmetric(root *TreeNode) bool {
	return isMirror(root, root)
}

func isMirror(a *TreeNode, b *TreeNode) bool {
	if a == nil && b == nil {
		return true
	}
	if a == nil || b == nil {
		return false
	}
	if a.Val != b.Val {
		return false
	}

	return isMirror(a.Left, b.Right) && isMirror(a.Right, b.Left)
}

相似题目

题目	难度	考察点
101. 对称二叉树	简单	递归、镜像
226. 翻转二叉树	简单	递归
104. 二叉树的最大深度	简单	递归
100. 相同的树	简单	递归
572. 另一棵树的子树	简单	树匹配

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/96501204