Преобразовать двоичное дерево в двусвязный список - Java - PullRequest
Новая
       41

Преобразовать двоичное дерево в двусвязный список - Java

0 голосов
/ 17 ноября 2018

Помогите мне с этой проблемой, пожалуйста.Он взят из курса Educative.io, который называется «Coderust 3.0: ускоренная подготовка к интервью»

Описание проблемы:

Преобразование двоичного дерева в двусвязный список таким образом, чтобыпорядок двусвязного списка такой же, как и в порядке обхода двоичного дерева.После преобразования левый указатель узла должен указывать на предыдущий узел в двусвязном списке, а правый указатель должен указывать на следующий узел в двусвязном списке.

Here's a visualization of the problem

Мой код: 

class toDLL{
  public static BinaryTreeNode convert_to_linked_list(BinaryTreeNode root) {

    Stack<BinaryTreeNode> stack = new Stack<>();
    BinaryTreeNode head = root;
    if(root == null) return head;

    while(root != null) {
      head = root;
      stack.push(root);
      root = root.left;
    }

    while(!stack.isEmpty()) {
      BinaryTreeNode temp = stack.pop();
      BinaryTreeNode cur = temp;

      cur = cur.right;
      while(cur != null) {
         stack.push(cur);
        cur = cur.left;
      }
      if(!stack.isEmpty()) {
        temp.right = stack.peek();
        stack.peek().left = temp;
      }
    }
    return head;
  }
}

Когда я запускаю его в компиляторе educative.io, я получаю следующую ошибку: 

Exception in thread "main" java.lang.NullPointerException
    at BinaryTree.get_list(*.java:39)
    at EdTestRunner.executeTests(*.java:374)
    at TestRunner.main(*.java:401)

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

Я не понимаю, как я могу получить исключение Null Pointer, когда у меня так много проверок, которые видят, еслистек пуст перед выполнением каких-либо операций.

Помогите пожалуйста

...