java - 删除具有特定值的子树

Question

我要解决的问题是给定一棵二叉树，删除与传递的参数值具有相同值的子树。这是我的代码，但我认为它不起作用，因为更改后的树与原始树完全相同。

Before:
              5
            /   \
          3       2
         / \     / \
        2   1   4   3

After removal of subtree of value 2:
              5
            /
           3      
            \    
             1  

public TreeNode removeSubtree(TreeNode root, int value){
    TreeNode copy = root;
    removeSubtreeRecursion(copy, value);
    return root;
}

public void removeSubtreeRecursion(TreeNode root, int val){
    if(root == null) return;
    else if(root.val == val) root = null;
    else{
        removeSubtreeRecursion(root.left, val);
        removeSubtreeRecursion(root.right, val);
    }
}

Answer 1

您可以使用父节点而不是当前节点来修改它。它可能是这样的:

public TreeNode removeSubtree(TreeNode root, int value){
    if (root != null && root.val == value) return null;
    removeSubtreeRecursion(root, value);
    return root;
}

public void removeSubtreeRecursion(TreeNode parent, int val) {
    if (parent.left != null && parent.left.val == val) parent.left = null;
    else removeSubtreeRecursion(parent.left, val);
    if (parent.right != null && parent.right.val == val) parent.right = null;
    else removeSubtreeRecursion(parent.right, val); 
}

在您的实现中，root = null 修改本地引用。您可以在 Pass by reference in Java 中阅读更多相关信息.