Java中删除特定树的节点有几种方法？如何高效地实现？

在Java中删除一颗树通常意味着从数据结构中移除一个节点或者整棵树,以下是几种常见情况下删除树的方法：

使用递归删除树

假设我们有一个二叉树,以下是如何递归删除一个节点的示例代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public class BinaryTree {
    TreeNode root;
    // 删除一个节点
    public void deleteNode(int value) {
        root = deleteNodeRecursive(root, value);
    }
    private TreeNode deleteNodeRecursive(TreeNode current, int value) {
        if (current == null) {
            return null;
        }
        if (value == current.val) {
            // 节点只有一个孩子或没有孩子
            if (current.left == null) {
                return current.right;
            } else if (current.right == null) {
                return current.left;
            }
            // 节点有两个孩子，找到右子树的最小值或左子树的最大值
            int smallestValue = findSmallestValue(current.right);
            current.val = smallestValue;
            current.right = deleteNodeRecursive(current.right, smallestValue);
        } else if (value < current.val) {
            current.left = deleteNodeRecursive(current.left, value);
        } else {
            current.right = deleteNodeRecursive(current.right, value);
        }
        return current;
    }
    // 找到右子树的最小值
    private int findSmallestValue(TreeNode root) {
        return root.left == null ? root.val : findSmallestValue(root.left);
    }
}

使用迭代删除树

在某些情况下,递归可能不是最佳选择，比如在内存受限的环境中，以下是使用迭代方法删除节点的示例：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public class BinaryTree {
    TreeNode root;
    // 删除一个节点
    public void deleteNode(int value) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.val == value) {
                // 节点只有一个孩子或没有孩子
                if (node.left == null && node.right == null) {
                    node = null;
                } else if (node.left == null) {
                    node.val = node.right.val;
                    node.right = null;
                } else if (node.right == null) {
                    node.val = node.left.val;
                    node.left = null;
                } else {
                    int smallestValue = findSmallestValue(node.right);
                    node.val = smallestValue;
                    node.right = deleteNode(node.right, smallestValue);
                }
                break;
            }
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
    private int findSmallestValue(TreeNode root) {
        return root.left == null ? root.val : findSmallestValue(root.left);
    }
    private TreeNode deleteNode(TreeNode root, int value) {
        if (root == null) {
            return null;
        }
        if (value == root.val) {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            int smallestValue = findSmallestValue(root.right);
            root.val = smallestValue;
            root.right = deleteNode(root.right, smallestValue);
        } else if (value < root.val) {
            root.left = deleteNode(root.left, value);
        } else {
            root.right = deleteNode(root.right, value);
        }
        return root;
    }
}

FAQs

Q1：如何删除二叉树中的所有节点？

A1：要删除二叉树中的所有节点，可以使用递归方法，从根节点开始，递归删除每个节点，直到没有节点为止，以下是删除所有节点的示例代码：

public void deleteTree(TreeNode node) {
    if (node == null) {
        return;
    }
    deleteTree(node.left);
    deleteTree(node.right);
    node = null; // 清除引用，以便垃圾收集器可以回收内存
}

Q2：如何删除二叉搜索树中的重复节点？

A2：在二叉搜索树中删除重复节点，可以通过在插入时检查节点是否已存在来实现，以下是删除重复节点的示例代码：

public TreeNode deleteDuplicates(TreeNode root) {
    if (root == null) {
        return null;
    }
    root.left = deleteDuplicates(root.left);
    root.right = deleteDuplicates(root.right);
    if (root.left != null && root.left.val == root.val) {
        root = root.right; // 删除重复的左节点
    } else if (root.right != null && root.right.val == root.val) {
        root = root.left; // 删除重复的右节点
    }
    return root;
}