Вам дан узел root бинарного дерева поиска (BST) и узел value для вставки в дерево. Вернуть корневой узел BST после вставки. Гарантируется, что новое значение не существует в исходном BST.
Обратите внимание, что может существовать несколько допустимых способов вставки, если после вставки дерево остается BST. Вы можете вернуть любой из них.
Пример 1:
Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5] Explanation: Another accepted tree is:
Решение:
В данной задаче нам нужно вставить значение val в двоичное дерево поиска.
В двоичном дереве поиска мы знаем, что левое поддерево меньше корня, а правое поддерево больше корня.
Итак, для вставки мы будем сравнивать val с корнем и, соответственно, вставлять его в дерево.
Во-первых, мы создадим новый узел для возврата значения.
TreeNode* node = new TreeNode(val);
Теперь нам нужно проверить, является ли корневойузел нулевым или нет. Если да, то верните новый узел, который мы создали на предыдущем шаге.
if(root == NULL)
return node;
Следующим шагом является сравнение val с корневым узлом. Если val меньше root, вставьте его в левое поддерево, а если val больше root, то он будет вставлен в правое поддерево.
if(root -> val > val)
root->left = insertIntoBST(root -> left, val);
else
root -> right = insertIntoBST(root -> right, val);
Наконец, будет возвращен корень.
return root;
Ниже приведен полный код проблемы:
Спасибо за прочтение!
S.
