📃 题目描述

题目链接：剑指 Offer 26. 树的子结构 (opens new window)

🔔 解题思路

乍一看和 572. 另一棵树的子树 (opens new window) 好像是一样的，但其实子树和子结构是不同的！

举个例子：

所谓 root2 是否是 root1 的子结构，其实就是从 root2 开始遍历，对应的从 root1 开始，从否匹配到 root2 上的所有节点。

所以这道题其实是一道 DFS 问题~

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }

        // 先从根节点判断 B 是不是 A 的子结构，如果不是在分别从左右两个子树判断，
        // 只要有一个为true，就说明 B 是 A 的子结构
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    // dfs 判断 root2 是否是以 root1 为根节点的树的子结构
    // 就是从 root2 开始遍历，对应的从 root1 开始，从否匹配到 root2 上的所有节点
    private boolean dfs(TreeNode root1, TreeNode root2) {
        // 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true
        if (root2 == null) {
            return true;
        }
        // 当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false
        // 或者 A.val != B.val，匹配失败，返回 false
        if (root1 == null || root1.val != root2.val) {
            return false;
        }
        
        // 当前节点比较完之后还要继续判断左右子节点
        return dfs(root1.left, root2.left) && dfs(root1.right, root2.right);
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：