Найти правых детей в двоичном дереве java

Question

У меня возникли проблемы с поиском последнего элемента (самого правого ребенка) в моем двоичном дереве.

Это то, что я до сих пор:

public Node findLastElement(Node root) { 
    Node x = root; 
    if (x != null) 
     findLastElement(x.right); 
    return x; 
} 

Если я печатаю элементы, последний один, который печатает последний элемент, но я не могу показаться, чтобы «получить» этот элемент. Когда я пытаюсь вернуть x после цикла, я получаю nullpointer. Как сохранить последний элемент и вернуть его?

Answer 1

Вы можете получить самый правый элемент рекурсивно как таковой:

public Node findLastElement(Node root) { 
    if (root == null) { 
     return null; 
    } 
    if (root.right == null) { 
     return root; 
    } 
    return findLastElement(root.right); 
} 

Вы также можете сделать это итеративно. Итерация обычно лучше с точки зрения памяти, потому что у нее нет дополнительных стековых кадров, созданных с рекурсией.

public Node findLastElement(Node root) { 
    if(root == null) { 
     return null; 
    } 
    Node x = root; 
    while(x.right != null) { 
     x = x.right; 
    } 
    return x; 
} 

И нет особой необходимости для переменной темп x. Поскольку java передает ссылку по значению (они являются копией исходной ссылки), любое присваивание, которое мы делаем во входном аргументе root, является локальным и не отражается вне метода findLastElement.

public Node findLastElement(Node root) { 
    if(root == null) { 
     return null; 
    } 
    while(root.right != null) 
     root = root.right; 
    return root; 
} 

Answer 2

Вам необходимо вернуть результат вызова рекурсивной функции.

E.g.

public Node findLastElement(Node x) { 
    if (x != null && x.right != null) 
     return findLastElement(x.right); 
    else 
     return x; 
} 

Answer 3

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

public Node findLastElement(Node root) { 
    Node x = root; 
     if(x != null){ 
      if (x.right != null) 
       return findLastElement(x.right); 
     } 
    return x; 
} 

Answer 4

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

public Node findLastElement(Node root) { 
    Node x = root; 

    if (x != null && x.right != null) { 
     return findLastElement(x.right); 
    } else { 
     return x; 
    } 

} 

Answer 5

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

public Node findLastElement(Node root) { 
    return root != null && root.right != null ? findLastElement(root.right) : root; 
}