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;
}