在 java 中迭代地破坏二叉树

Question

该任务一般在递归post顺序遍历时完成，网上例子很少。其中之一是here，但我想知道它是否正确，因为_deleteTree()方法似乎只做了一个BFS而没有对节点做任何操作，删除是通过简单地将树的根设置为无效的。毫无疑问 return 一棵空树。但是删除对所有树节点的引用是正确的方法吗？

此外，对于迭代post顺序遍历，比如下面

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

通常，当您将节点分配给 null 时，从技术上讲，您会删除所有数据。与链接列表一样，当您通过将其 "next" per say 设置为 null 来断开其连接时，您将删除该列表，而 java 垃圾收集器将负责其余部分。因此，在您链接的 Java 代码中，一旦确定根没有 children，它们就会做同样的事情。

Answer 2

有一个更好的解决方案，它使用树节点本身来存储队列。像这样：

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;
        }
    }
}

在 java 中迭代地破坏二叉树

destroying a binary tree iteratively in java

java

algorithm

binary-tree

destroy