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() を記述して、指定されたツリーからいくつかのノードを削除します ..!

! の場合にのみ削除するように pop ノードを記述します。NewHead に等しい。

したがって、ツリーから値をポップし、それを New Head を Head ノードとする New 二分探索ツリーに挿入します。

したがって、ツリーから要素を削除して、新しい検索ツリーに追加します。

ツリー ヘッド ポイント NewHead まで。

したがって、すべての要素は、次のようになる New head を指す二分探索ツリーにあります。

明らかにソートされた順序で。

このようにして、 O(NlogN) でのソートを約束します。

于 2013-04-01T13:34:30.823 に答える
2

分析

二分木の定義を考えると、次のようになります。

各ノードには、親、L 子、および R 子があります。

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（深さ優先検索）を探していると思います。深さ優先検索のアイデアは、バックトラックする前に隣人から隣人へできるだけ深く移動することです。可能な深さを決定するのは、エッジをたどる必要があり、どの頂点にも 2 回アクセスしないことです。

ブーストはすでにそれを提供しています：こちらを参照してください

于 2013-05-27T10:32:08.217 に答える
0

クイックソートを使用します。

ノードは複数の配列の最下位レベルでソートされ、ソートされた要素のこれらの配列は最後にマージされます。

例えば

関数 quick_sort(ノード n)
1. 左モードに移動し、null でない場合は、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 に答える