首页 > 代码库 > 020给定两个二叉树T1,T2判断T1是否是T2的子树(keep it up)
020给定两个二叉树T1,T2判断T1是否是T2的子树(keep it up)
给定两个二叉树T1,T2判断T1是否是T2的子树
首先在T2中查找T1的根节点,如果找不到,
则T1不是T2的子树,如果能找到,我们可以
遍历T1,检查T1的每个结点是否对应的存在T2
首先在T2中查找T1的根节点,如果找不到,
则T1不是T2的子树,如果能找到,我们可以
遍历T1,检查T1的每个结点是否对应的存在T2
中。
代码:
struct TreeNode { int data; TreeNode* leftChild; TreeNode* rightChild; }; bool isExited(const TreeNode* vRoot1, const TreeNode *vRoot2, TreeNode* vRes) { if (vRoot1 == NULL) return false; if (vRoot2 == vRoot1) { vRes = vRoot1; return true; } bool Flag = false; Flag = isExited(vRoot1, vRoot2->leftChild, vRes); if (!Flag) { Flag = isExited(vRoot1, vRoot2->rightChild, vRes); } return Flag; } bool isSame(const TreeNode* vRoot1, const TreeNode *vRoot2) { if (vRoot1 == NULL && vRoot2 == NULL) return true; if (vRoot1 != vRoot2) return false; bool Flag = isSame(vRoot1->leftChild, vRoot2->leftChild); if (!Flag) return false; Flag = isSame(vRoot1->rightChild, vRoot2->rightChild); return Flag; } bool isSubTree(const TreeNode* vRoot1, const TreeNode *vRoot2) { TreeNode* Temp = NULL; //保存在T2中的位置 if (!isExited(vRoot1, vRoot2, Temp)) return false; return isSame(vRoot1, Temp); }
020给定两个二叉树T1,T2判断T1是否是T2的子树(keep it up)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。