3.2.36

上次更新:2019-10-08
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

用一个栈来模拟递归即可,将路径上的结点记录到栈里。
注意 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 库

上一题 下一题