3.2.36

3.2.36 #

解答 #

用一个栈来模拟递归即可，将路径上的结点记录到栈里。

注意 Queue<TKey> 不算额外空间，因为它在keys执行完毕之后不会被回收。

代码 #

private void Keys(Node x, Queue<TKey> queue, TKey lo, TKey hi)
{
    var stack = new Stack<Node>();

    while (x != null || stack.Count > 0)
    {
        if (x != null)
        {
            var cmpLo = lo.CompareTo(x.Key);
            var cmpHi = hi.CompareTo(x.Key);
            if (cmpHi >= 0)
                stack.Push(x);
            if (cmpLo < 0)
                x = x.Left;
            else
                x = null;
        }
        else
        {
            x = stack.Pop();
            var cmpLo = lo.CompareTo(x.Key);
            var cmpHi = hi.CompareTo(x.Key);
            if (cmpLo <= 0 && cmpHi >= 0)
                queue.Enqueue(x.Key);
            x = x.Right;
        }
    }
}

另请参阅 #

BinarySearchTree 库