题解 | #树的子结构#
树的子结构
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: bool recursion(TreeNode* root1, TreeNode* root2){ //当一个节点存在另一个不存在时 if(root1 == NULL && root2 != NULL) return false; //两个都为空则返回 if(root1 == NULL || root2 == NULL) return true; //比较节点值 if(root1->val != root2->val) return false; //递归比较子树 return recursion(root1->left, root2->left) && recursion(root1->right, root2->right); } bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { //空树 if(pRoot2 == NULL) return false; //一个为空,另一个不为空 if(pRoot1 == NULL && pRoot2 != NULL) return false; if(pRoot1 == NULL || pRoot2 == NULL) return true; //递归比较 bool flag1 = recursion(pRoot1, pRoot2); //递归树1的每个节点 bool flag2 = HasSubtree(pRoot1->left, pRoot2); bool flag3 = HasSubtree(pRoot1->right, pRoot2); return flag1 || flag2 || flag3; } };
两层前序遍历,第一层前序遍历遍历树A,判断每个根节点对应的子树和树B一不一样。第二层前序遍历用来具体判断两个树是不是完全一样。