LeetCode 剑指 Offer 26. 树的子结构

Categories:

题目描述
思路分析
1. 解法一：DFS 匹配（推荐）
相似题目

题目描述

✅ 剑指 Offer 26. 树的子结构

思路分析

解法一：DFS 匹配（推荐）

核心思路：

子结构要求 B 在 A 的某个子树中结构和值都匹配。

先遍历 A 的每个节点作为起点；若当前值相等则尝试匹配。

匹配函数：B 为空则成功，A 为空则失败，否则继续比较左右子树。

复杂度分析：

时间复杂度：O(n * m)，其中 n、m 分别为 A、B 节点数。

空间复杂度：O(h)，其中 h 为树高度，递归栈占用。

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return match(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

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

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil || B == nil {
		return false
	}
	return match(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

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

相似题目

题目	难度	考察点
572. 另一棵树的子树	简单	DFS
100. 相同的树	简单	DFS
101. 对称二叉树	简单	DFS
235. 二叉搜索树的最近公共祖先	简单	树
236. 二叉树的最近公共祖先	中等	树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/85666181