уничтожение двоичного дерева итеративно в java

Question

Задача обычно выполняется во время рекурсивного обхода после ордера, и есть несколько примеров онлайн. Один из них - here, но мне интересно, правильно ли это, потому что метод _deleteTree() выполняет только BFS и не выполняет никаких операций с узлами, а удаление выполняется простым набором корня дерева в null. Это, без сомнения, вернет пустое дерево. Но правильно ли это удалить ссылки на все узлы дерева?

Кроме того, для итеративного обхода после заказа, скажем, как показано ниже

public TreeNode postorderTraversal(TreeNode root) { 
    if(root==null) return null; 
    Stack<TreeNode> stack1=new Stack<>(); 
    Stack<TreeNode> stack2=new Stack<>(); 
    TreeNode cur=root; 
    stack1.push(cur); 
    while(!stack1.isEmpty()){ 
     cur=stack1.pop(); 

     if(cur!=null){ 
      stack2.push(cur); 
     } 

     if(cur.left!=null){ 
      stack1.push(cur.left); 
     } 
     if(cur.right!=null){ 
      stack1.push(cur.right); 
     } 
    } 

    while(!stack2.isEmpty()){ 
     //elements poped will be in post order sequence 
     } 
    return root; 
} 

Как уничтожить бинарное дерево итеративно? Может кто-нибудь дать пример кода (java)? Спасибо!

Answer 1

Существует лучшее решение, которое использует сами узлы дерева для хранения очереди. Что-то вроде этого:

static void clear(Node root) { 
    while (root != null) { 
     Node left = root.left; 
     if (left == null) { 
      Node right = root.right; 
      root.right = null; 
      root = right; 
     } else { 
      // Rotate the left child up. 
      root.left = left.right; 
      left.right = root; 
      root = left; 
     } 
    } 
} 

Answer 2

Обычно, когда вы назначаете нулевой узел, вы технически избавляетесь от всех данных. Как со связанным списком, когда вы нарушаете его соединение, устанавливая его «следующий» для каждого слова в null, вы удаляете список, а сборщик мусора java заботится обо всем остальном. Таким образом, в коде Java, который вы связали, они делают то же самое, как только корень будет иметь детей.