15

这是我最近在一次采访中被问到的一个问题。给出一棵二叉树，条件是每个左孩子比根小 1，右孩子比根大 1。这是一个示例树

一颗树

以 O(1) 和 O(n) 的时间复杂度对其进行排序。

以下是我建议的方法：

  1. 使用计数来维护每个元素的计数，然后在完成整个遍历后返回 O(n) 时间和 O(n) 空间复杂度。
  2. 使用游程编码。当元素以数字为键，以计数为值重复时形成链。仅当 no 重复时才需要空间用于计数，因此除了数组之外不需要额外的空间，但时间复杂度将为 O(n log n)，因为我们必须遍历数组以查看它是否存在。
  3. 最后我建议广度优先遍历。我们需要 O(log n) 的队列空间和 O(n) 的时间复杂度（假设插入是 O(1) 链表）。

你的方法是什么？

4

5 回答 5

2

将给定树的某些叶节点修复为 NewHead 。

编写一个函数 Pop() 从给定的树中删除一些节点..！

编写弹出节点，以便您仅在它存在时将其删除！等于 NewHead 。

因此，从树中弹出值，将其插入到以 New Head 作为 Head 节点的 New 二叉搜索树中。

因此，您将从树中删除一个元素，将其添加到新的搜索树中。

直到树头点 NewHead 。

所以你所有的元素现在都在指向新头的二叉搜索树中，这将是

显然是按顺序排列的。

这种方式保证你在 O(NlogN) 中进行排序。

于 2013-04-01T13:34:30.823 回答
2

分析

鉴于您对二叉树的定义，我们有以下内容，

每个节点都有一个 Parent、L-child 和 R-child .. 其中：

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 = Left-child of 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

建议的解决方案

这个问题似乎很复杂，但我的解决方案将在以遍历顺序 Left-Right-Parent 插入值后使用合并排序，这将有助于合并排序在其平均情况和最佳情况之间获得时间复杂度，但使用一个小技巧我在上面所做的比较。

首先，我们使用 Left-Right-Parent 遍历将树节点收集到一个列表中，考虑到以下事实：并且假设当我们每次向左侧移动时，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);
        }
    }
}
于 2013-05-27T08:46:28.177 回答
1

我猜，您正在寻找 DFS（深度优先搜索）。在深度优先搜索中，想法是在回溯之前从邻居到邻居尽可能深入。决定可能有多深的是您必须遵循边，并且您不会两次访问任何顶点。

boost 已经提供了它：见这里

于 2013-05-27T10:32:08.217 回答
0

使用快速排序。

节点在多个数组中的最低级别排序，这些排序元素的数组最后合并。

例如

函数 quick_sort(node n)
1. 进入左模式，如果不为空，就调用 quick_sort。
2. 到右边的元素，如果不为null，调用quick_sort就可以了。
3.合并左节点排序&右节点排序&当前节点的结果。
4. 返回合并后的数组。

于 2013-04-08T08:51:07.387 回答
-1

我没有得到这个问题。二叉树不是已经排序了吗？如果您想按顺序打印出项目（或按顺序访问它们），此代码将起作用

/**
* 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) 复杂性。要返回列表而不是打印，只需创建一个并通过将子项添加到列表来替换每个 show 语句

于 2013-03-29T04:14:34.143 回答