有没有办法在不使用任何其他存储(如数组)的情况下在二叉搜索树中找到所有可能的完整路径和中的第 k 个最大的?最初我认为,如果我在增加指针的同时继续从右侧找到路径的总和,每个新的总和都是最小值,而前一个总和(最初总和是无限的),当计数达到 时就会中断k
。但是我刚刚发现,虽然最大叶值自然地从右到左排序,但总和不必如此。所以这个方法行不通。我怎样才能做到这一点?
问问题
246 次
有没有办法在不使用任何其他存储(如数组)的情况下在二叉搜索树中找到所有可能的完整路径和中的第 k 个最大的?最初我认为,如果我在增加指针的同时继续从右侧找到路径的总和,每个新的总和都是最小值,而前一个总和(最初总和是无限的),当计数达到 时就会中断k
。但是我刚刚发现,虽然最大叶值自然地从右到左排序,但总和不必如此。所以这个方法行不通。我怎样才能做到这一点?