root двоичного дерева поиска (все значения различны: в левом поддереве каждой вершины значения меньше, в правом — больше) и число key. Удалите из дерева вершину со значением key и верните корень получившегося дерева.
Удалять нужно строго по такому правилу:
- если вершины с key нет, дерево не меняется;
- если у удаляемой вершины нет детей или есть только один ребёнок, на её место встаёт этот ребёнок (или ничего);
- если детей двое, на её место встаёт правый ребёнок, а всё левое поддерево подвешивается левым ребёнком к самой маленькой вершине правого поддерева.
Постарайтесь уложиться в время, пропорциональное высоте дерева.root=tree_node([10, 5, 15, 3, 8, None, 20]), key=5 → [10, 8, 15, 3, None, None, 20]
У вершины 5 два ребёнка. Её место занимает правый ребёнок 8, а левое поддерево (вершина 3) подвешивается левым ребёнком к самой маленькой вершине правого поддерева — это сама 8.
root=tree_node([10, 5, 15, 3, 8, None, 20]), key=15 → [10, 5, 20, 3, 8]
У вершины 15 только правый ребёнок, он и встаёт на её место.
root=tree_node([10, 5, 15]), key=7 → [10, 5, 15]
Ключа 7 в дереве нет — дерево не меняется.
root — корректное дерево поискаroot=tree_node([10, 5, 15, 3, 8, None, 20]), key=5
[10, 8, 15, 3, None, None, 20]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 63 теста на сервере, включая скрытые.