输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ /
4 5
/ /
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000
解:其实这道题的思路 就是递归的判断两个树的结点是否相同，如果不相同再用左子树的左节点或者右节点判断递归的判断，难搞的点在于如何处理B树为空应该返回false的情况，我自己写的 如下 ，但有两个结点没通过
/** * 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 isSubStructure(TreeNode* A, TreeNode* B) { if(A==nullptr&&B==nullptr) { return true; } if(A==nullptr&&B!=nullptr) { return false; } if(B==nullptr) { return true; } if(A->val==B->val) { return isSubStructure(A->left,B->left)&&isSubStructure(A->right,B->right); } return isSubStructure(A->left,B)||isSubStructure(A->right,B); } };
看了看别人的答案想了想，还是得额外加一个函数
class Solution { public: bool isSubStructure(TreeNode* A, TreeNode* B) { //考虑开始的时候是否为空 if(A==nullptr||B==nullptr) return false; return dfs(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B); } bool dfs(TreeNode* A, TreeNode* B) { //走到这里b为空说明B数走完了 if(B==nullptr) { return true; } if(A==nullptr) { return false; } return (A->val==B->val)&&dfs(A->left,B->left)&&dfs(A->right,B->right); } };
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/17549.html