这是我最近在一次面试中被问到的问题。给定一个二叉树，条件是每个左子节点比根节点小1，每个右子节点比根节点大1。以下是一个示例树：
在O(1)和O(n)时间复杂度内进行排序。
以下是我提出的方法：
你有什么方法吗？
分析
根据您对二叉树的定义，我们有以下内容：
每个节点都有父节点、左子节点和右子节点，其中：
L < N
R > N
P > N
L < N AND R > N => L < N < R => L < R
L < N AND P > N => L < N < P => L < P
R > N AND P > N => N < MIN(P,R)
N < MIN(P,R) AND L < N => L < N < MIN(P,R)
现在让我们尝试扩展它，N.L = N的左子节点：
N.L < N
N.R > N
N.P > N
N.L.L < N.L < MIN(N, N.L.R)
N.L.R > N.L > N.L.L
N.R.L < N.R < MIN(N, N.R.R)
N.R.R > N.R > N.R.L
IF N IS N.P LEFT-CHILD: N < N.P < MIN(N.P.P, N.P.R)
IF N IS N.P RIGHT-CHILD: N > N.P.R
提出的解决方案
这个问题看起来很复杂，但我的解决方案是在按照左-右-父节点的遍历顺序插入值后使用归并排序，这将帮助归并排序获得一个时间复杂度，介于其平均情况和最优情况之间，但通过使用我上面所做的比较技巧，可以使其更加高效。
首先，我们使用左-右-父节点遍历将树节点收集到一个列表中，考虑到：N.L < N < MIN(N.R, N.P)，并且给父节点赋予更高的权重，假设 O(N.R) <= O(N.P)，每次向左移动时，值会线性减少，.. > N.R.R > N.R > N > N.L > N.L.L > ..。
在按照该遍历顺序收集树节点后，列表将具有一些已排序的块，这将有助于我们接下来要使用的归并排序。
此解决方案的时间复杂度为：Time = O(n log n + n)，空间复杂度为：Space = O(n)
以下是Java语言编写的算法（未经测试）：
private class Node Comparable<Node>
{
public Node R;
public Node L;
public int value;
public Node (Node L, int val, Node R)
{
this.L = L;
this.value = val;
this.R = R;
}
@Override
public int compareTo(Node other)
{
return ((other != null) ? (this.value-other.value) : 0);
}
}
class Main
{
private static Node head;
private static void recursive_collect (Node n, ArrayList<Node> list)
{
if (n == null) return;
if (n.left != null) recursive_collect (n.L, list);
if (n.right != null) recursive_collect (n.R, list);
list.add(n.value);
}
public static ArrayList<Node> collect ()
{
ArrayList<Node> list = new ArrayList<Node>();
recursive_collect (head, list);
return list;
}
// sorting the tree: O(n log n + n)
public static ArrayList<Node> sortTree ()
{
// Collecting nodes: O(n)
ArrayList<Node> list = collect();
// Merge Sort: O(n log n)
Collections.sort(list);
return list;
}
// The example in the picture you provided
public static void createTestTree ()
{
Node left1 = new Node (new Node(null,-2,null), -1, new Node(null,0,null));
Node left2 = new Node (new Node(null,-1,null), 0, new Node(null,1,null));
Node right = new Node (left2, 1, new Node(null,2,null));
head = new Node (left1, 0, right);
}
// test
public static void main(String [] args)
{
createTestTree ();
ArrayList<Node> list = sortTree ();
for (Node n : list)
{
System.out.println(n.value);
}
}
}
将给定树的一些叶节点作为NewHead修复。
编写一个函数Pop()从给定树中删除某些节点..!
编写弹出节点的代码，以便仅在其不等于NewHead时才将其删除。
因此，从树中弹出值，将其插入到以Head节点为New Head的新二叉搜索树中。
因此，您将从树中删除一个元素并将其添加到新的搜索树中。
直到树头指向NewHead为止。
这样可以保证O(NlogN)的排序方式。
因此，现在所有元素都在二叉搜索树中，该二叉搜索树指向New Head，并且显然按排序顺序排列。
我猜你正在寻找深度优先搜索算法（DFS）。
在深度优先搜索中，从相邻的节点开始尽可能深入地遍历，直到回溯。决定能够走多深的因素是必须沿着边缘移动，并且不重复访问任何顶点。
boost已经提供了它：可以看看这里。
使用快速排序。
节点在多个数组的最底层进行排序，这些排好序的元素数组在最后合并。
例如：
函数quick_sort(node n)
1. 如果左侧节点不为空，则进入左侧模式并调用quick_sort。
2. 如果右侧节点不为空，则进入右侧模式并调用quick_sort。
3. 合并左侧节点排序和右侧节点排序及当前节点的结果。
4. 返回合并后的数组。
我不太明白这个问题。二叉树不是已经排序了吗？如果你想按顺序打印出项目（或按顺序访问它们），这段代码可以工作。
/**
* Show the contents of the BST in order
*/
public void show () {
show(root);
System.out.println();
}
private static void show(TreeNode node) {
if (node == null) return;
show(node.lchild);
System.out.print(node.datum + " ");
show(node.rchild);
}
我相信这将是O(n)的复杂度。如果要返回一个列表而不是打印，只需创建一个列表，并通过将子项添加到列表中来替换每个显示语句。