Add One Row to Tree
Easy C++ Kotlin PythonEnunciado do problema
Dada a raiz de uma árvore binária, em seguida, valor v e profundidade d, é necessário adicionar uma linha de nós com o valor v na profundidade dada d. O nó raiz está na profundidade 1.
A regra de adição é: dada uma profundidade inteira positiva d, para cada nó da árvore NÃO nulo N na profundidade d-1, crie dois nós de árvore com o valor v como raiz da subárvore esquerda de N e raiz da subárvore direita. E a subárvore esquerda original de N deve ser a subárvore esquerda da nova raiz da subárvore esquerda, sua subárvore direita original deve ser a subárvore direita da nova raiz da subárvore direita. Se a profundidade d for 1, significa que não há profundidade d-1, crie um nó de árvore com o valor v como a nova raiz de toda a árvore original e a árvore original é a subárvore esquerda da nova raiz.
Solução
Supondo que a estrutura do nó da árvore seja:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x){
val = x;
left = NULL;
right = NULL;
}
}
O problema pode ser resolvido recursivamente tratando os casos básicos:
- d-1 = 0 : Essa condição significa que precisamos adicionar uma nova raiz à árvore. Crie um novo nó e faça com que ele faça root com a raiz real como filhos esquerdos.
- d-1 = 1 : Este nó é pai dos novos nós que serão adicionados. Crie dois novos nós para esquerda e direita e crie os respectivos filhos antigos do pais filhos esquerdo e direito.
- d-1 > 1 : Neste caso, é necessário ir mais fundo na árvore. Verifique se a criança existe e se positiva chama a mesma função com o valor de profundidade menos 1.
Com essas informações, a seguinte implementação é feita:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if(d-1==0){
TreeNode* newRoot = new TreeNode(v);
newRoot->left = root;
return newRoot;
}
if(d-1==1){
TreeNode *newleft = new TreeNode(v), *newright = new TreeNode(v);
newleft->left = root->left;
newright->right = root->right;
root->left = newleft;
root->right = newright;
}else{
if(root->left) addOneRow(root->left,v,d-1);
if(root->right)addOneRow(root->right,v,d-1);
}
return root;
}
Complexidade de tempo: O(n)
question from LeetCode