首页 文章

在java中迭代地销毁二叉树[复制]

提问于
浏览
0

这个问题在这里已有答案:

该任务通常在递归的邮件订单遍历期间完成,并且在线的示例很少 . 其中一个是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)吗?谢谢!

2 回答

  • 0

    有一个更好的解决方案,它使用树节点本身来存储队列 . 像这样的东西:

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

    通常,当您将节点分配为null时,您在技术上会删除所有数据 . 与链接列表一样,当您通过将其“下一个”设置为null来断开其连接时,您将删除该列表,而Java垃圾收集器将处理其余的事务 . 所以在你链接的Java代码中,一旦确定root没有子代,他们就会做同样的事情 .

相关问题