c++ - 在 C++ 中解释类型为 'int' 的递归函数的返回值

Question

无法理解如何使用 int 类型的递归函数查找二叉搜索树的高度的解释。

对于任何二叉搜索树，给定一个指向树的根节点的指针，其中节点通常定义如下...

struct Node {
    int data;
    Node* left;
    Node* right;
}
Node* root;

我们可以使用以下 int 类型的递归函数来为我们提供二叉搜索树的高度...(函数“max”只接受两个 int 并返回两者中较大的一个)

int findHeight(Node* root){
    if(root == NULL){
        return -1;
    }
    return max(findHeight(root->left),findHeight(root->right)) + 1;
}

int max(int a, int b){
    if (a > b)
        return a;
    else
        return b;
}

我的理解是findHeight(root->left)求root的左子树的高度，findHeight(root->right)求root的右子树的高度，然后max返回哪个大，因为这将是树的总高度，加上 1 以包括将根连接到该子树的边。

我对递归还很陌生，所以我决定只拆解其中一个递归函数调用并尝试理解它。我以一种伪代码的方式写出了 findHeight(root->left) ，每次函数调用自身时都会在其中包含“PAUSE”一词，以表示堆栈上发生的事情并缩进下一个函数调用以显示一个新的堆栈框架...(在我的示例 BST 中，左子树的高度为 2)

int fH(Node* root){
    if(root == NULL)
        return -1;

    fH(root->left);
    PAUSE

    int fH(Node* root){
        if root == NULL)
            return -1;

        fH(root->left);
        PAUSE

        int fHR(Node*root){
            if (root == NULL)
                return -1;

            fH(root->left);
            PAUSE

            int fHR(Node* root){
                if (root == NULL)
                    return -1;

                fH(root->left);
                PAUSE

                int fHR(Node* root){
                if(root==NULL)
                    return -1;
                }
            }
        }
    }
}

函数运行正常，但我不明白函数的返回值是如何从-1(函数最终执行返回的值)增长到 2 的。递归 int 函数是否将其返回值加 1每次返回到之前的栈帧时的值？

我在那个短函数中没有看到任何增加函数返回值的东西。我唯一看到的是最后一次调用是 -1。

如果有人可以尝试向我解释这一点，我将非常感谢您的帮助。非常感谢。

Answer 1

函数 findHeight 返回当前找到的最大高度。

考虑到这一点，最大调用是合理的。

在此 Action 重演中，我们得到以下函数调用。

1. 调用节点 1。我们希望在左侧找到 2 个深度。右手边还有一个。所以 max，将有希望在左侧做出决定。最大调用 Node2 和 node3
2. 在第 4 点中讨论了对 2 的调用。
3. 调用 3 返回 0。-1 和 -1 的最大值，+1。最大值为 -1，加一。
4. 到节点2的findHeight，将有max of(left node (-1)), and right node 4) Item 5 + 1.
5. max of -1, -1 +1 = 0。所以这使得点 4 的最大值为 1。

所以最后函数 findHeight 说，这是我当前检查的结束(0 高度)。以前的函数调用可以将他们喜欢的任何内容添加到我的函数调用中。

在我看来，这个函数可以用更直观的方式来编写。

也许

int treeHeight(Node* node){
    if (!node) // We are not a node.
        return 0;
    int weAreANode = 1;  // Height 1.
    int heightLeft = treeHeight(node->left);
    int heightRight = treeHeight(node->right);
    int theHighestSubtreeHeight = std::max(heightLeft, heightRight);

    return weAreANode + theHighestSubtreeHeight;
}

我真的只是想重新画东西。