删除具有特定值的子树

Remove Subtree with specific value(删除具有特定值的子树)

问题描述

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

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);
    }
}

推荐答案

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

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中阅读有关此内容的更多信息。

这篇关于删除具有特定值的子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！