1

问题是，给定一个 BST，找出是否有两个数字加起来等于一个给定的数字k。不应使用额外的内存。

现在，如果它是一个排序数组，我可以简单地保留两个指针，一个在开头，一个在结尾。在每一步，我都会计算指针指向的两个数字的总和，如果总和小于 k，我会增加起始指针，否则会减少结束指针，直到匹配或指针重叠。

我可以对 BST 做同样的事情，通过中序遍历将其转换为排序数组，但这需要额外的内存。所以我认为迭代器解决方案是有序的。我会保留两个迭代器，一个会以正常的中序方式遍历 BST，调用它将返回下一个更大的数字，另一个会以逆序方式遍历 BST，在每次调用时返回下一个较小的数字。

知道如何设计这样的迭代器吗？我更喜欢 Python/Javascript 的解决方案。虽然 Python 提供了类似的函数iter，但我想使用闭包来设计它。

4

2 回答 2

3

This kind of iterators (using closures) are called generators in python.

Generators are functions, using 'yield' keyword instead of 'return'. When yield is encountered, the respective value is returned, but the execution state of the function is suspended, until the next value is required.

So, you can just implement a tree-traversal function, using 'yield' instead of 'return', and your goal will be accomplished.

They are very easy to design:

# 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

Output:

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

To manually iterate, use:

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 回答