[双重DFS]面试题26. 树的子结构

面试题26. 树的子结构"/>

[双重DFS]面试题26. 树的子结构

题目：

题解：

• 坑点：A、B为空树，这两棵树都不相等。。。
• 剩下的用两层dfs解决，第一层dfs用来判断B是否是A的左子树或右子树，第二层dfs来判断B是否是A的子结构。
• 类似题：572. 另一个树的子树

代码如下：

class Solution {
public:bool isSubStructure(TreeNode* A, TreeNode* B) {if(!A||!B)return false;//A、B有一个为空，表示匹配失败；或者A、B都为空，这两颗树也不相等if(isSame(A,B))return true;return isSubStructure(A->left,B)||isSubStructure(A->right,B);}bool isSame(TreeNode* A,TreeNode* B){if(!B)return true;//B为空，A是否空，都完成匹配了if(!A)return false;//B为不空，A为空，匹配失败if(A->val!=B->val)return false;return isSame(A->left,B->left)&&isSame(A->right,B->right);}
};