如何在非二叉搜索树的普通二叉树中删除值为最大值的节点？

看起来你已经搞定了最大值查找的部分，但删除逻辑确实需要调整——你的当前removeMax方法只处理了根节点是最大值的情况，而且递归的条件判断也有点问题，没法正确定位到非根的最大值节点并完成删除。我来帮你梳理下思路，然后给出修正后的实现。

先说说你现有removeMax的问题 #

• 递归触发条件错误：你只在当前节点值不等于最大值且左右子树都存在时才递归，但实际上只要当前节点不是最大值，不管左/右子树是否存在，只要有子树就应该递归下去，不然会漏掉很多情况。
• 缺少非根节点的删除逻辑：你只处理了根节点是最大值的情况，但如果最大值在某个子节点上，你没有找到它的父节点来修改引用，自然没法删除。
• 没考虑最大值节点的子树情况：比如最大值节点可能有左/右子树，删除时需要把这些子树正确挂载到父节点上。

修正后的实现思路 #

要删除最大值节点，我们需要：

1. 先找到最大值（你已经实现findMax了，这部分没问题）。
2. 遍历树，找到最大值节点的父节点，以及该节点是父节点的左子还是右子节点。
3. 根据最大值节点的子树情况做删除操作：
   • 如果最大值节点是叶子节点：直接把父节点对应的左/右子引用设为null。
   • 如果最大值节点只有左子树：把父节点的对应子引用替换成该节点的左子树。
   • 如果最大值节点只有右子树：把父节点的对应子引用替换成该节点的右子树。
   • 如果最大值节点是根节点：把root设为它的左/右子树（如果有的话），没有就设为null。
   • 如果最大值节点同时有左右子树：普通二叉树没有BST的规则限制，我们可以选择左子树的最大值或右子树的最小值来替换原节点，保证树的结构完整。

完整代码实现 #

我把你的代码修改并补充完整，添加了辅助方法来处理节点定位和子树替换逻辑：

public class MyLinkedBinaryTree extends LinkedBinaryTree {
    MyLinkedBinaryTree() {
        super();
    }

    // 对外暴露的删除最大值方法，无需用户传参
    public void removeMax() {
        if (root == null) {
            return; // 空树直接返回
        }
        int maxValue = findMax(root);
        // 查找最大值节点、其父节点及子节点类型（左/右）
        NodeInfo nodeInfo = findTargetNodeAndParent(root, null, maxValue);
        if (nodeInfo.targetNode == null) {
            return; // 理论上不会触发，因为findMax已确认最大值存在
        }

        // 执行删除逻辑
        if (nodeInfo.parentNode == null) {
            // 目标节点是根节点
            root = getReplacementNode(nodeInfo.targetNode);
        } else {
            // 根据子节点类型修改父节点的引用
            if (nodeInfo.isLeftChild) {
                nodeInfo.parentNode.leftChild = getReplacementNode(nodeInfo.targetNode);
            } else {
                nodeInfo.parentNode.rightChild = getReplacementNode(nodeInfo.targetNode);
            }
        }
    }

    // 辅助方法：递归查找目标节点、其父节点及是否为左子节点
    private NodeInfo findTargetNodeAndParent(BinaryTreeNode current, BinaryTreeNode parent, int targetValue) {
        if (current == null) {
            return new NodeInfo(null, null, false);
        }
        if ((int) current.element == targetValue) {
            return new NodeInfo(current, parent, parent != null && parent.leftChild == current);
        }
        // 先查左子树，找到就返回
        NodeInfo leftResult = findTargetNodeAndParent(current.leftChild, current, targetValue);
        if (leftResult.targetNode != null) {
            return leftResult;
        }
        // 左子树没找到，查右子树
        return findTargetNodeAndParent(current.rightChild, current, targetValue);
    }

    // 辅助方法：获取删除节点后的替换节点（处理子树挂载）
    private BinaryTreeNode getReplacementNode(BinaryTreeNode node) {
        // 只有左子树，直接返回左子树
        if (node.rightChild == null) {
            return node.leftChild;
        }
        // 只有右子树，直接返回右子树
        if (node.leftChild == null) {
            return node.rightChild;
        }
        // 同时有左右子树：选择左子树的最大值作为替换节点（也可选右子树最小值）
        int leftMax = findMax(node.leftChild);
        NodeInfo leftMaxInfo = findTargetNodeAndParent(node.leftChild, node, leftMax);
        // 先删除左子树中的最大值节点
        if (leftMaxInfo.isLeftChild) {
            leftMaxInfo.parentNode.leftChild = getReplacementNode(leftMaxInfo.targetNode);
        } else {
            leftMaxInfo.parentNode.rightChild = getReplacementNode(leftMaxInfo.targetNode);
        }
        // 将替换节点的左右子树替换为原节点的子树
        leftMaxInfo.targetNode.leftChild = node.leftChild;
        leftMaxInfo.targetNode.rightChild = node.rightChild;
        return leftMaxInfo.targetNode;
    }

    // 你的findMax方法逻辑正确，保留使用
    public int findMax(BinaryTreeNode t) {
        if (t == null) return 0;
        int res = (int) t.element;
        int lres = findMax(t.rightChild);
        int rres = findMax(t.leftChild);
        if (lres > res) res = lres;
        if (rres > res) res = rres;
        return res;
    }

    // 内部辅助类：存储节点相关信息
    private static class NodeInfo {
        BinaryTreeNode targetNode;
        BinaryTreeNode parentNode;
        boolean isLeftChild;

        NodeInfo(BinaryTreeNode target, BinaryTreeNode parent, boolean isLeft) {
            this.targetNode = target;
            this.parentNode = parent;
            this.isLeftChild = isLeft;
        }
    }
}

代码说明 #

1. 对外方法removeMax()：封装了所有逻辑，用户无需传参即可调用，使用更友好。
2. findTargetNodeAndParent：递归遍历树，精准定位最大值节点及其父节点，同时标记节点类型，为后续修改父节点引用提供依据。
3. getReplacementNode：处理不同子树场景的节点替换逻辑，尤其针对同时有左右子树的情况，通过选择左子树最大值来保证树结构的完整性（你也可以根据需求改为右子树最小值）。
4. 原有的findMax方法逻辑正确，直接保留使用。

这样修改后，不管最大值节点在树的哪个位置（根、叶子、中间节点），都能正确完成删除操作。

内容的提问来源于stack exchange，提问作者Г. Лувсангомбо