Удалить поддерево с определенным значением

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 изменяет локальную ссылку.Подробнее об этом можно прочитать в Передача по ссылке в Java .