2022-12-28-数元灵科技-实习面试-34min
判断一个树是否是另一个树的子树,本来是直接判断指向的是否是同一个节点,后说值相同也可以,就改了下
#include <iostream> struct node { node *leftChild, *rightChild; int32_t v; node(node *l, node *r, int32_t value) : leftChild(l), rightChild(r), v(value) {} }; bool isSame(node *a, node *b) { if ((a == nullptr) != (b == nullptr)) return false; if (a == nullptr) return true; if (a->v != b->v) return false; return isSame(a->leftChild, b->leftChild) && isSame(a->rightChild, b->rightChild); } bool isChildTree(node *childRoot, node *parentRoot) { if (childRoot == nullptr) return true; if (parentRoot == nullptr) return false; if (isSame(childRoot,parentRoot)) return true; return isChildTree(childRoot, parentRoot->leftChild) | isChildTree(childRoot, parentRoot->rightChild); } int main() { node *a = new node(nullptr, nullptr, 1); node *b = new node(nullptr, nullptr, 2); node *root = new node(a, b, 0); node *c = new node(nullptr, nullptr, 3); node *d = new node(nullptr, nullptr, 4); a->leftChild = c; std::cout << "c is a subTree of root: " << isChildTree(c, root) << "\n"; std::cout << "d is a subTree of root: " << isChildTree(d, root) << "\n"; delete c,d,a,b; return 0; }#实习##面试##24实习#