递归返回和不返回的区别

Question

我写了一个程序来打印二叉树根部的第 K 个节点。

// PRINT KTH NODE FROM ROOT (FUNCTION 1)
void printKth(node *root, int k){
    if (root == NULL){
        return;
    }
    if (k == 0){
        cout<<root -> data<<" ";
        return;
    }

    printKth(root -> left, k-1);
    printKth(root -> right, k-1);
}

对于下面的二叉树，代码打印

//          100     
//         /   \
//       80     120
//      /  \
//    40    60
// 
// OUTPUT - 80 120

在我在倒数第二行和倒数第三行添加 return 语句之前，上述函数工作正常。

// PRINT KTH NODE FROM ROOT (FUNCTION 2)
void printKth(node *root, int k){
    if (root == NULL){
        return;
    }
    if (k == 0){
        cout<<root -> data<<" ";
        return;
    }

    return printKth(root -> left, k-1);    // ADDED RETURN STATEMENT
    return printKth(root -> right, k-1);   // ADDED RETURN STATEMENT
}

对于下面的二叉树，代码打印

//          100     
//         /   \
//       80     120
//      /  \
//    40    60
// 
// OUTPUT - 80

我不明白添加 return 语句时发生了什么。

Answer 1

递归函数没有什么特别之处。第二个你 return 你不再评估其余的。你会在你的基本案例中看到这一点，因为他们不会评估其余的。当您添加 return 时，调用的结果是 returned 并且永远不会到达最后一个语句。

在您的第一个版本中，您的函数不打印第 k 个节点，而是打印第 k 个级别中的每个节点。如果要打印第 k 个节点，则必须 return 当前 k，如果它仍然为正，则继续递归到正确的树中。

递归返回和不返回的区别

Difference between returning and not returning in recursion

c++

tree

recursion