c++ - 如何在深度优先搜索的递归实现中返回 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 返回值。有没有返回 bool 值的地方？

此外，我正在寻找递归解决方案，而不是迭代解决方案。

Answer 1

您的执行方式与调用其他函数而不是递归的方式完全相同。
(递归的大 secret 在于递归没有什么特别之处。)

树是相等的当且仅当

• 节点相等，并且
• 它的两个子树都相等

所以

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

作为练习处理剩余的空箱子。