面试题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);}
};
更多推荐
[双重DFS]面试题26. 树的子结构
发布评论