1

並べ替えられたリンク リストをバランスのとれた BST に変換するために Java でこのコードを見ていましたが、実装 #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/ を持ち歩くか、含まれているクラスに何らかのイテレーターを組み込む必要があります。これにより、LHS の構築中のソースリストの進行が親に返されます。 & 祖父母などに返される前に RHS を構築するために使用されます。

言語に複数の値が返される場合は、(BinaryTree.Node, MyList.Node) を返し、そのタプルの 2 番目のフィールドを使用して作業の進行状況を追跡できます。

本質的に、あなたはすでに解決策をハックしています - あなたが構造化されていないものとは対照的に、 W をIteratorにすれば、それはきれいで正しいでしょう。

于 2013-05-10T04:10:29.500 に答える