如何在深度优先搜索的递归实现中返回bool？

Question

我想编写一个函数来检查两个二叉树是否相同.

代码如下:

bool checkSame(Node* first, Node* second) {
    // Check if nodes are the same

    // Check left nodes: checkSame(first->left, second->left)
    // Check right nodes: checkSame(first->right, second->right)

}

问题是我不知道该返回什么地方.我发现的所有DFS实现都有一个void返回值.有没有一个它返回一个布尔？

另外,我正在寻找递归解决方案,而不是迭代解决方案.

Answer 1

你这样做的方式与调用其他函数而不是递归的方式完全相同.
(递归的一个大秘密就是递归没什么特别的.)

树木是相等的,当且仅当

• 节点是相等的,和
• 它的子树都是平等的

所以

return first->data == second->data 
    && checkSame(first->left, second->left)
    && checkSame(first->right, second->right);

处理作为练习留下的空箱子.