0

Java でバイナリ ツリーの最小高と最大高を取得する 2 つの方法があります。しかし、ルートを 2 回トラバーサルしています。それぞれですlog n in Big(O)。同じトラバーサルで最小値と最大値の両方を計算し、最小値と最大値に対応する 2 つのインデックスを持つ配列として返す方法はありますか。

ここに私の方法があります

public static int minHeight(Node root){
            if (root==null) return -1;
            return 1+Math.min(minHeight(root.left), minHeight(root.right));
        }

public static int height(Node root){
            if (root==null) return -1;
            return 1+Math.max(height(root.left), height(root.right));

        }

class Node {
        Node left;
        Node right;
        int data;

        public Node(int c){
            this(c, null, null);
        }
        public Node(int c,Node left, Node right) {
            this.data = c;
            this.left=left;
            this.right=right;
        }


    }
4

4 に答える 4

2

1 回のパスで高さを計算し、最小値と最大値を追跡します。あなたの混乱は、関数が単一の値を返すという事実にありますが、実際には値のペアを決定する必要があります。したがって、たとえば、結果を格納できるフィールドを持つオブジェクトを渡し、関数の戻り値ではなくそれを介して結果を返すことができます。

class MinMax {
    public int min;
    public int max;
}

void computeMinMaxHeight (Node root, MinMax minmax) {
    // update the fields of minmax accordingly
}

のフィールドを初期化する便利な方法は次のMinMaxとおりです。

class MinMax {
    public int min = Integer.MAX_VALUE;
    public int max = Integer.MIN_VALUE;
}

または、初期化されていないことを示すフラグを追加して、最初の項目の値が正しく入力されるようにします。

編集: int[2]Changgeng が示唆するように、配列を返すこともできます。それは、意味的により適切だと思うものに依存します。個人的には、MinMax(Java には値の範囲を表すための標準クラスが実際にはありません) のようなものを選び、さらに出力パラメーターを関数に渡すことで、オブジェクトの割り当てを節約できます (重要な場合)。

于 2013-11-06T02:25:58.873 に答える
1

Big(O) の主張は正しくありません。実装では、ツリー内のすべてのノードにアクセスする必要があるため、時間の複雑さはO(n).

レベル オーダー ツリー トラバーサルは 1 回で答えを出すことができますが、それを正しく行うには 2 つのキューが必要です。

public int[] findMinMax(Node node) {
    Queue<Node> currentLevel = new LinkedList<Node>();
    Queue<Node> nextLevel = new LinkedList<Node>();

    currentLevel.offer(node);
    int currentHeight = 1;

    int[] result = new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
    while (!currentLevel.isEmpty() || !nextLevel.isEmpty()) {

        if (currentLevel.isEmpty()) {
            currentHeight += 1;
            Queue<Node> tmp = nextLevel;
            nextLevel = currentLevel;
            currentLevel = tmp;
        }

        node = currentLevel.poll();
        if (node.left != null) {
            nextLevel.offer(node.left);
        }
        if (node.right != null) {
            nextLevel.offer(node.right);
        }
        if (node.left == null && node.right == null) {
            result[0] = Math.min(result[0], currentHeight);
        }
    }

    result[1] = currentHeight;

    return result;


}

とは言っても、普段は本当にもったいないですよね。再帰的なソリューションは、記述と理解がはるかに簡単です。

于 2013-11-06T02:40:15.840 に答える
0

ノードの最小高さと最大高さを示す各ノードに常に 2 つのプロパティを設定できます。 

  this.max = Math.max(this.left.max,this.right.max) + 1 ; 
  this.min = Math.min(this.left.min,this.right.min) + 1;
于 2013-11-06T02:18:21.590 に答える