如何在二叉搜索树(BST)中递归打印所有叶节点的父节点

现有代码核心问题 #

• 缺少递归终止判断：未处理cur为空指针的场景，直接访问cur->right/cur->left会触发空指针访问，是段错误的直接诱因
• 递归逻辑错误：左子树被重复调用遍历，且部分分支直接return会跳过右子树的遍历，导致只能输出第一侧的符合条件节点
• 代码冗余：两个重载的printLeafParent逻辑完全重复，无必要单独实现无参版本的逻辑

正确实现思路 #

对二叉树做全量遍历，每访问一个节点执行两个操作：

1. 判断当前节点的左/右子节点是否为叶子节点，只要任意一个是叶子，就打印当前节点的key
2. 递归遍历当前节点的左子树、右子树，查找子树中符合条件的父节点

修复后代码 #

// 递归工具函数
void BST::printLeafParent(Tnode* cur) {
    // 递归终止条件：当前节点为空直接返回
    if (cur == nullptr) {
        return;
    }
    bool hasLeafChild = false;
    // 判断左孩子是不是叶子
    if (cur->left != nullptr && getHeight(cur->left) == 0) {
        hasLeafChild = true;
    }
    // 判断右孩子是不是叶子
    if (cur->right != nullptr && getHeight(cur->right) == 0) {
        hasLeafChild = true;
    }
    // 符合条件就打印
    if (hasLeafChild) {
        cout << cur->key << " ";
    }
    // 递归遍历左右子树
    printLeafParent(cur->left);
    printLeafParent(cur->right);
}

// 外层调用函数
void BST::printLeafParent() {
    printLeafParent(root);
}

可选优化点 #

如果getHeight接口需要递归计算高度会额外增加时间开销，可以直接判断子节点是不是叶子：叶子节点的左右指针都为空，所以直接把判断逻辑替换为cur->left != nullptr && cur->left->left == nullptr && cur->left->right == nullptr即可，不需要调用getHeight，性能更高。

内容的提问来源于stack exchange，提问作者user17275949