自己制作免费网站wordpress 首页 未登录

树的子结构

---

输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。

我们规定空树不是任何树的子结构。

数据范围

每棵树的节点数量 $[0,1000]$。

样例

树 A：

     8/ \8   7/ \9   2/ \4   7

树 B：

   8/ \9   2

返回 true，因为 B 是 A 的子结构。

---

算法思路

第一部分：遍历树A

• 递归遍历树A中的所有非空节点R
• 对每个非空节点R，进行第二部分的匹配判断

第二部分：子树匹配判断

同时从根节点开始遍历两棵子树：

1. 终止条件：
   • 如果树B中的节点为空 → 匹配成功，返回true
   • 如果树A中的节点为空但树B不为空 → 匹配失败，返回false
   • 如果两节点都不为空但值不同 → 匹配失败，返回false
2. 递归判断：
   • 当前节点匹配成功后，递归判断左右子树：

时间复杂度分析

• 最坏情况：需要遍历树A中的每个节点（n个），对每个节点都要完整遍历树B（m个）
• 时间复杂度：O(n×m)
  • n：树A的节点数
  • m：树B的节点数

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if(!pRoot1 || !pRoot2) return false;if(dfs(pRoot1, pRoot2)) return true;return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);}bool dfs(TreeNode* p1, TreeNode* p2){if(!p2) return true;if(!p1 || p1->val != p2->val) return false;return dfs(p1->left, p2->left) && dfs(p1->right, p2->right);}
};