Как вернуть дважды связанный список и удалить листья дерева?

Question

Я работал над задачей, подобной SPOJ. Цель состояла в том, чтобы найти листья в двоичном дереве (не обязательно BST), удалить их из дерева и вернуть их как своего рода дважды связанный список, используя ту же структуру - TreeNode и никаких дополнительных импортов. Например, если узлы 2, 4 и 3 удалены из дерева, функция возвращает первый ненулевой элемент списка: null < - 2 < -> 4 < -> 3 -> null. TreeNode имеет значение и указатели влево и вправо.

Я использовал рекурсию и аннулировал листья, чтобы удалить их из дерева и воссоздал их в списке. Чтобы добавить элемент в конец списка, я удерживал указатель на последний элемент списка. Это создало хорошо известную проблему изменения объекта, переданного функции. Вот мой код:

public TreeNode getLeaves(TreeNode root) 
{ 
    if(root == null) 
     return null; 

    TreeNode start = new TreeNode(Integer.MIN_VALUE); 
    TreeNode[] end = {start}; 
    getLeaves(root, start, end); 
    return start; 
} 

private void getLeaves(TreeNode root, TreeNode start, TreeNode[] end) 
{ 
    if(root == null) 
     return; 

    if(root.left == null && root.right == null) 
    { 
     addToList(root, start, end); 
     root = null; 
     return; 
    } 
    getLeaves(root.left, start, end); 
    getLeaves(root.right, start, end); 
} 

private void addToList(TreeNode element, TreeNode start, TreeNode[] end) 
{ 
    if(end[0].value != Integer.MIN_VALUE) 
    { 
     TreeNode t = new TreeNode (element.value); 
     end[0].right = t; 
     t.left = end[0]; 
     end[0] = t; 
    } 
    else 
    { 
     start.value = element.value; 
    } 
} 

Удаление листьев из дерева не работает, но список возвращается правильно. Однако, установив значение «start» TreeNode на минимальное значение int вместо использования пустых ссылок, я также использую массив. Использование Atomic Reference сделает его более беспорядочным IMHO. Я совершенно уверен, что есть способ сделать это гораздо более изящным способом (и удалять листья должным образом), возможно, путем изменения подхода назначения начального и конечного TreeNodes. Я чувствую, что что-то не так с моим подходом и/или пониманием того, как все это работает. Не могли бы вы помочь мне превратить его в аккуратный фрагмент кода и объяснить мои неудачи?

Answer 1

У вас есть ошибка во второй функции GetLeaves. В заявлении root = null; задается значение локальной переменной root, но ее родитель будет хранить ссылку на лист.

У вас будет намного удобнее время, если вы добавите метод bool isLeaf() в TreeNode. Я изменил ваш код на то, что, как я думаю, может работать.

private bool isLeaf() 
{ 
    // This method should be in TreeNode 
    return left == null && right == null; 
} 
// Also, TreeNode should have an Add(TreeNode) method 

public TreeNode getLeaves(TreeNode root) 
{ 
    if(root == null) // check if the whole tree is empty 
     return null; // return something relevant here 
    else if(root.isLeaf()) 
     return root; //cannot remove this leaf, unfortunately 
    TreeNode leaves = new TreeNode() 
    getLeaves(root, leaves); 
    return leaves; 
} 
private void getLeaves(TreeNode current, TreeNode leaves) 
{ 
    // current is guaranteed to be non-null and not a leaf itself. 
    if(current.left.isLeaf()) { 
     leaves.add(current.left); 
     current.left = null; 
    } else { 
     getLeaves(current.left, leaves); 
    } 
    if(current.right.isLeaf()) { 
     leaves.add(current.right); 
     current.right = null; 
    } else { 
     getLeaves(current.right, leaves); 
    } 
} 

Answer 2

Давид, вы на 100% прав. Спасибо за помощь. В случае, если кто-то задается вопросом, вот самое изящное решение, которое я произвел до сих пор, включая улучшение Дэвида. Единственное, что я не уверен в том, должен ли метод addToList быть статичным или, возможно, более правильным/универсальным назвать его в контексте элемента.

public TreeNode getLeaves(TreeNode root) 
{ 
    if(root == null) 
     return null; 

    if(root.isLeaf()) 
     return root; 

    TreeNode[] listEdges = {null, null}; 
    getLeaves(root, listEdges); 
    return listEdges[0]; 
} 

private void getLeaves(TreeNode root, TreeNode[] edges) 
{ 
    if(root == null) 
     return; 

    if(root.left != null && root.left.isLeaf()) 
    { 
     addToList(edges, root.left); 
     root.left = null; 
    } 

    if(root.right != null && root.right.isLeaf()) 
    { 
     addToList(edges, root.right); 
     root.right = null; 
    } 
    getLeaves(root.left, edges); 
    getLeaves(root.right, edges); 
} 

private static void addToList(TreeNode[] edges, TreeNode element) 
{ 
    if(edges[1] != null) 
    { 
     edges[1].right = element; 
     element.left = edges[1]; 
     edges[1] = element; 
    } 
    else 
    { 
     edges[0] = element; 
     edges[1] = edges[0]; 
    } 
} 

public boolean isLeaf() 
{ 
    return this.right == null && this.left == null; 
}