Easy

题目描述

给你两棵二叉树 root 和 subRoot，检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true；否则，返回 false。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

解题思路

这道题需要判断一棵树是否是另一棵树的子树。我们可以使用递归的方法来解决。

核心思路：

  1. 两层递归结构：外层递归遍历主树的每个节点，内层递归判断当前节点为根的子树是否与目标子树相同
  2. 判断两树是否相同：需要一个辅助函数来判断两棵树是否完全相同（结构和节点值都相同）

具体步骤：

  1. 首先处理边界情况：如果 subRoot 为空，返回 true；如果 root 为空而 subRoot 不为空，返回 false
  2. 对于主树的每个节点，检查以该节点为根的子树是否与 subRoot 相同
  3. 如果当前节点匹配失败，继续递归检查左右子树
  4. 判断两树相同的条件：根节点值相等，且左右子树也分别相同

时间复杂度优化： 虽然最坏情况下需要 O(m×n) 的时间复杂度，但在实际应用中，大部分不匹配的情况会很快被剪枝，平均性能较好。

这种方法简洁直观，易于理解和实现，是解决此类树结构匹配问题的经典方法。

代码实现

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!subRoot) return true;
        if (!root) return false;
        
        return isSameTree(root, subRoot) || 
               isSubtree(root->left, subRoot) || 
               isSubtree(root->right, subRoot);
    }
    
private:
    bool isSameTree(TreeNode* s, TreeNode* t) {
        if (!s && !t) return true;
        if (!s || !t) return false;
        
        return s->val == t->val && 
               isSameTree(s->left, t->left) && 
               isSameTree(s->right, t->right);
    }
};

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        if not root:
            return False
        
        return (self.isSameTree(root, subRoot) or 
                self.isSubtree(root.left, subRoot) or 
                self.isSubtree(root.right, subRoot))
    
    def isSameTree(self, s: Optional[TreeNode], t: Optional[TreeNode]) -> bool:
        if not s and not t:
            return True
        if not s or not t:
            return False
        
        return (s.val == t.val and 
                self.isSameTree(s.left, t.left) and 
                self.isSameTree(s.right, t.right))

public class Solution {
    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) return true;
        if (root == null) return false;
        
        return IsSameTree(root, subRoot) || 
               IsSubtree(root.left, subRoot) || 
               IsSubtree(root.right, subRoot);
    }
    
    private bool IsSameTree(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        
        return s.val == t.val && 
               IsSameTree(s.left, t.left) && 
               IsSameTree(s.right, t.right);
    }
}

var isSubtree = function(root, subRoot) {
    if (!root) return false;
    return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

function isSameTree(p, q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)其中 m 是主树节点数，n 是子树节点数。最坏情况下需要对主树的每个节点都进行完整的子树比较
空间复杂度O(max(m, n))递归调用栈的深度，最坏情况下等于较深树的高度

相关题目