1

問題は、BSTが与えられた場合、与えられた数に合計される2つの数があるかどうかを調べることkです。余分なメモリは使用しないでください。

これで、並べ替えられた配列の場合、最初に1つ、最後に1つ、合計2つのポインターを保持できたはずです。各ステップで、ポインターが指す2つの数値の合計を計算します。合計がk未満の場合は、開始ポインターをインクリメントします。そうでない場合は、一致するか、ポインターがオーバーラップするまで終了ポインターをデクリメントします。

BSTでも同じことができ、順序付けられたトラバーサルによってソートされた配列に変換できますが、追加のメモリが必要になります。したがって、イテレータソリューションが適切だと思います。2つのイテレータを保持します。1つは通常の順序でBSTをトラバースし、呼び出して次に大きい番号を返し、もう1つはBSTを逆順序でトラバースして、呼び出しごとに次に小さい番号を返します。

そのようなイテレータを設計する方法はありますか？私はPython/Javascriptのソリューションを好みます。Pythonはのような関数を提供しますがiter、クロージャを使用して設計したいと思います。

4

2 に答える 2

3

この種の (クロージャーを使用する) イテレーターは、Python ではジェネレーターと呼ばれます。

ジェネレーターは関数であり、「return」の代わりに「yield」キーワードを使用します。yield が発生すると、それぞれの値が返されますが、関数の実行状態は、次の値が必要になるまで中断されます。

したがって、「return」の代わりに「yield」を使用して、ツリー トラバーサル関数を実装するだけで、目的が達成されます。

設計は非常に簡単です。

# Simple tree definition
class Tree:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# In-order lazy iterator (aka generator)
def inorder(tree):
    if tree is not None:
        for x in inorder(tree.left):
            yield x
        yield tree.data
        for x in inorder(tree.right):
            yield x

# Reverse in-order lazy iterator
def rev_inorder(tree):
    if tree is not None:
        for x in rev_inorder(tree.right):
            yield x
        yield tree.data
        for x in rev_inorder(tree.left):
            yield x

# Construct a tree
n1 = Tree(1)              
n2 = Tree(2)              
n3 = Tree(3)              #         7
n4 = Tree(4)              #       /   \
n5 = Tree(5, n1, n2)      #     5       6
n6 = Tree(6, n3, n4)      #    / \     / \
n7 = Tree(7, n5, n6)      #   1   2   3   4

for i in inorder(n7):
    print i, 
print

for i in rev_inorder(n7):
    print i, 
print

出力：

1 5 2 7 3 6 4
4 6 3 7 2 5 1

手動で反復するには、次を使用します。

gen = rev_inorder(n7)
print gen.next()       # Output 4
print gen.next()       # Output 6
于 2012-12-14T13:26:38.637 に答える
0

簡単なアイデアを思いつきます ;-): BST の周りの反復に余分なスペースを割り当てたくない場合は、パフォーマンスを犠牲にする必要があります。

var inst = new BST();
inst.Insert(-121);
inst.Insert(13);
inst.Insert(1);
inst.Insert(10);
GetAddends(inst, 55); // here we go
function GetAddends(bst, target) {
    var iter1 = bst.GetIterator();
    var iter2 = bst.GetIterator(false);

    while (iter1.IsValid() && iter2.IsValid() && (iter1.Pos() < iter2.Pos())) {
        var temp = iter1.data() + iter2.data();
        if (temp < target) iter1.Next();
        else if (temp > target) iter2.Next();
        else window.alert(iter1.data() + "+" + iter2.data() + "=" + target);
    }
    bst.ClearIterators();
}

function BST() {
    var _root, _nodeCount, _locked;
    this.Insert = function(data) { 
        if (_locked === true) throw "could not modify the BST during iteration";
        _nodeCount++;
    }
    this.Delete = function(data) {
        if (_locked === true) throw "could not modify the BST during iteration";
        _nodeCount--;
        return null;
    }
    this.GetIterator = function(isForward) { return Iter(isForward); }
    this.ClearIterators = function() { _locked = false; }

    function Iter(isForward) {
        if (isForward == null) isForward = true; // if the parameter is omitted, then true by default
        _locked = true;
        var _pos = isForward ? 0 : (_nodeCount - 1);
        var _curData;
        return function() {
            this.IsValid() {
                return (isForward ? (_pos < _nodeCount) : (_pos >= 0));
            }
            this.Next = function() {
                isForward ? _pos++ : _pos--;
                _curData = null;
            }
            this.Pos = function() { return _pos; }
            this.Data = function() {
                if (_curData == null) { /* loop the BST and find _posTH node and stored in the _curData in case we need it later */ }
                return _curData;
            }
        }
    }
}

コードは BST を実装していませんが、アイデアは明確です。楽しむ！ここで、イテレータを保持している最中に BST を変更することは許可されていないことに注意してください。保持イテレータの範囲外になったら、ClearIterators() を呼び出す必要があります。ただし、これに対する洗練された解決策は、PUB/SUB を使用して BST にイテレータがいくつ存在するかを知らせることです。たぶん、これは別の質問かもしれません。

于 2012-12-14T14:26:40.953 に答える