1

我正在查看 Java 中的这段代码，以将排序的链表转换为平衡的 BST，我想知道为什么实现 #1 不起作用。Java 的原因是什么，当我创建一个包装器对象并传递它时它可以完美地工作，但是当我使用本地引用时它却没有？对象仍然在堆右侧创建。

实施#1

BinaryTree.Node sortedListToBST(MyList.Node w, int start, int end) 
    {
          if (start > end) return null;
          int mid = start + (end - start) / 2;
          BinaryTree.Node left = sortedListToBST(w, start, mid-1);
          BinaryTree.Node parent = new BinaryTree.Node(w.getVal());
          w = w.getNext();
          BinaryTree.Node right = sortedListToBST(w, mid+1, end);
          parent.left = left;
          parent.right =right;
          return parent;
        }



        BinaryTree.Node sortedListToBST(MyList.Node head, int n) {

          return sortedListToBST(head, 0, n-1);
        }

实施#2

    BinaryTree.Node sortedListToBSTWrapper(Wrapper w, int start, int end) 
    {
          if (start > end) return null;
          int mid = start + (end - start) / 2;
          BinaryTree.Node left = sortedListToBSTWrapper(w, start, mid-1);
          BinaryTree.Node parent = new BinaryTree.Node(w.node.getVal());
          w.node = w.node.getNext();
          BinaryTree.Node right = sortedListToBSTWrapper(w, mid+1, end);
          parent.left = left;
          parent.right =right;
          return parent;
        }



        BinaryTree.Node sortedListToBSTWrapper(MyList.Node head, int n) {
             Wrapper w = new Wrapper();
                w.node = head;
          return sortedListToBSTWrapper(w, 0, n-1);
        }
4

1 回答 1

4

关键线是：

w.node = w.node.getNext();

在第一个实现中，递归级别中的“前进指针”被遗忘了；父母来电者看不到职位已经提高。

如果您想让第一种方法起作用，您需要携带一个 Iterator/ 或让包含类包含某种 Iterator ，以便在构建 LHS 时通过源列表的进步将返回给父级& 用于建造 RHS .. 在返回祖父母等之前。

如果语言有多值返回，您可以返回 (BinaryTree.Node, MyList.Node) 并使用该元组中的第二个字段来跟踪您的工作进度。

从本质上讲，您已经破解了一个解决方案——如果您将 W设为Iterator，它将是干净且正确的，而不是您只是想弄一个非结构化的东西。

于 2013-05-10T04:10:29.500 回答