algorithm - 删除二进制三中不位于 sum>= k 的任何路径中的所有节点

Question

无法理解此处给出的答案 有人可以帮助理解。

我的算法：

递归地找到每条路径的总和。如果 sum >=k，则将路径中的所有节点放入一个 hashset 中，最后遍历树，删除 hashset 中不存在的节点。

我很确定，这里有很多改进的余地。

Answer 1

你有树，你递归地解析它是这样的：

go_node(Node node){
  go_node(node.left);
  go_node(node.right);
}

在您的示例中，您想要删除任何值小于给定数字的子树。解决方法很简单，我们稍微改变一下简单的函数，问题就解决了。我让“K”成为全局变量，以使这段代码尽可能简单。但是，您也可以在 go_node 方法中解析它。

int go_node(Node node, int value){
  this.total_value = value;
  total_value += go_node(node.left, value);
  if (node.left.total_value < K){
     node.left = null;
  }
  total_value += go_node(node.right, value);
  if (node.right.total_value < K){
     node.right = null;
  }
  return total_value;
}

为什么我现在可以删除它们？当某个值从左子树或右子树返回时，该子树“完成”，它被处理并且重要的是 - 它让我添加了所有子树。所以当这个节点的total_value小于K时，这意味着这个节点和这个节点的所有孩子（以及孩子的孩子等）小于K。因为当子树孩子返回我一个值时，那个孩子有total_value存储所有子树的值。

Answer 2

方法是遍历树并以自下而上的方式删除节点。在遍历树的同时，递归计算每条路径从根节点到叶节点的节点总和。对于每个访问的节点，根据给定的总和“k”检查总计算总和。如果 sum 小于 k，则释放（删除）该节点（叶节点）并将总和返回给前一个节点。

public int removeNodesUtil(Node node, int sum, int k)
{
    if (node == null) return sum;

    sum =sum + node.data;
    if (node.left == null && node.right == null) 
    {
        if (sum < k)
        {
            node = null;
        }
        return sum;
    }
    int leftSum = 0, rightSum = 0, maxSum = 0;

    if (node.left != null) {
        leftSum = removeNodesUtil(node.left, sum, k);
        if (leftSum < k) {
            node.left = null;
        }
    }

    if (node.right != null) {
        rightSum = removeNodesUtil(node.right, sum, k);
        if (rightSum < k) {
            node.right = null;
        }
    }
    maxSum = Math.max(leftSum, rightSum);
    if (maxSum < k) {
        node = null;
    }
    return maxSum;
}