Рекурсивно удалять BST

Question

У меня есть BST и вы хотите закрепить дерево, как только будет достигнута определенная глубина. Когда я пытаюсь пересечь дерево, я сталкиваюсь с NullPointerException, устанавливая узлы за глубиной нулевой.

Является ли моя логика правильной с тем, что я здесь делаю? Это кажется довольно простой проблемой, но я не могу понять, что вызывает эту ошибку.

public void clip(int d) { 
    int counter = 0; 
    clip_helper(d, root, counter); 
} 

public void clip_helper(int depth, Node n, int c) { 

    if (n != null) { 
     c++; 
     if (c == depth) { 
      n.left = null; 
      n.right = null; 
     } 
    } 
    clip_helper(depth, n.left, c); 
    clip_helper(depth, n.right, c); 
} 

* Следует также добавить, что я довольно новичок в рекурсивных решениях, поэтому мне может быть что-то явно очевидное.

Answer 1

clip_helper(depth, n.left, c); 
clip_helper(depth, n.right, c); 

Эти строки вызывает исключение NullPointer как ваша программа никогда не заканчивается Даже если узел п нуль, оно все еще идет влево и вправо, которая вызывает этот

Чтобы решить эту проблему, просто добавьте нулевое состояние проверка на верхней части вашего кода

if(n==null) 
    return; 

Answer 2

Вы должны изменить:

clip_helper(depth, n.left, c); 
clip_helper(depth, n.right, c); 

к:

if(n.left!=null && n.right!=null) { 
    clip_helper(depth, n.left, c); 
    clip_helper(depth, n.right, c); 
} 

или:

if(c==depth) { 
    clip_helper(depth, n.left, c); 
    clip_helper(depth, n.right, c); 
} 

, так как рекурсивный вызов clip_helper не остановится.

Answer 3

Вы должны вернуться, если узел является нулевым, как показано ниже

public void clip(int d) { 
    int counter = 0; 
    clip_helper(d, root, counter); 
} 

public void clip_helper(int depth, Node n, int c) { 
    if(n== null) return; 
    if (n != null) { 
     c++; 
     if (c == depth) { 
      n.left = null; 
      n.right = null; 
     } 
    } 
    clip_helper(depth, n.left, c); 
    clip_helper(depth, n.right, c); 
}