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