删除 BST 范围内的叶节点
Delete leaf nodes between a range in BST
我想删除叶节点,其值超出给定范围(比如[L R])。我做了一个解决方案,我只是遍历所有节点并检查我当前的叶节点的值是否在给定范围内。如果不是,那么我将删除此节点。
我的做法-
private static Node trim(Node root, int L, int R) {
if (root == null)
return null;
if (root.left == null && root.right == null) {
if (root.val < L || root.val > R)
return null;
else
return root;
}
root.left = trim(root.left, L, R);
root.right = trim(root.right, L, R);
return root;
}
但这在 o(n) 内运行,因为我正在遍历所有节点(而且我没有在任何地方使用 BST 的 属性)。谁能帮我找到更好/优化的解决方案?
就像 m.raynal 说的,因为你只想删除叶子,所以你不能比 O(n) 更好。
只有当分支中的所有节点都在范围内时,您才能添加快捷方式,例如
private static Node trim(Node root, int L, int R) {
return trim(root, L, R, null,null);
}
private static Node trim(Node root, int L, int R, Integer lBound, Integer rBound)
{
if (root == null)
return null;
if (lBound != null && lBound >= L && rBound != null && rBound <= R ) {
return root;
}
if (root.left == null && root.right == null) {
if (root.val < L || root.val > R)
return null;
else
return root;
}
root.left = trim(root.left, L, R, lBound , root.val);
root.right = trim(root.right, L, R, root.val, rBound );
return root;
}
我想删除叶节点,其值超出给定范围(比如[L R])。我做了一个解决方案,我只是遍历所有节点并检查我当前的叶节点的值是否在给定范围内。如果不是,那么我将删除此节点。
我的做法-
private static Node trim(Node root, int L, int R) {
if (root == null)
return null;
if (root.left == null && root.right == null) {
if (root.val < L || root.val > R)
return null;
else
return root;
}
root.left = trim(root.left, L, R);
root.right = trim(root.right, L, R);
return root;
}
但这在 o(n) 内运行,因为我正在遍历所有节点(而且我没有在任何地方使用 BST 的 属性)。谁能帮我找到更好/优化的解决方案?
就像 m.raynal 说的,因为你只想删除叶子,所以你不能比 O(n) 更好。
只有当分支中的所有节点都在范围内时,您才能添加快捷方式,例如
private static Node trim(Node root, int L, int R) {
return trim(root, L, R, null,null);
}
private static Node trim(Node root, int L, int R, Integer lBound, Integer rBound)
{
if (root == null)
return null;
if (lBound != null && lBound >= L && rBound != null && rBound <= R ) {
return root;
}
if (root.left == null && root.right == null) {
if (root.val < L || root.val > R)
return null;
else
return root;
}
root.left = trim(root.left, L, R, lBound , root.val);
root.right = trim(root.right, L, R, root.val, rBound );
return root;
}