java - 再帰的二分木探索 MakePerfect x=change(x)

Question

IntTree クラスに追加できるメソッド makePerfect を作成するとします。メソッドは、バイナリ ツリーが「完全な」ツリーになるまでノードを追加する必要があります。完全な二分木とは、すべての葉が同じレベルにあるものです。もう 1 つの考え方は、ルートからリーフまでのすべてのパスが同じ長さになるまで、ツリーにダミー ノードを追加していることです。完全なツリーの形状は正確に三角形であり、すべての分岐ノードには正確に 2 つの子があります。ツリーに追加する各ノードには、値 0 を格納する必要があります。

前後の呼び出しの例:

私のコードはこれらのケースで機能します:

しかし、他の人は失敗します。このメソッドには、一度だけ呼び出すことができるヘルパー メソッドが含まれています。

// WRITE YOUR CODE HERE
public void makePerfect() {
    overallRoot = makePerfect(overallRoot, 1);
}

private IntTreeNode makePerfect(IntTreeNode root, int lvl) {
    if(root != null) {
        if( lvl < height(root) ) {
            if(root.left == null && root.right != null) {
                root.left = new IntTreeNode(0);
                root.left = makePerfect(root.left, lvl + 1);
                root.right = makePerfect(root.right, lvl +1);
            }if(root.right == null && root.left != null) {
                root.right = new IntTreeNode(0);
                root.right = makePerfect(root.right, lvl +1);
                root.left =makePerfect(root.left, lvl +1);
            }else if ( root.left == null && root.right == null) {
                root.left = new IntTreeNode(0);
                root.right = new IntTreeNode(0);
                lvl++;
            }else {
            root.left = makePerfect(root.left, lvl +1);
            root.right = makePerfect(root.right, lvl +1);
            }
        }
    }
    return root;
}




// LEAVE THESE METHODS HERE, TO USE AS HELPERS
public int height() {
    return height(overallRoot);
}

private int height(IntTreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return 1 + Math.max(height(root.left), height(root.right));
    }
}

テスト対象外のケースは? しばらくこれに固執していましたが、どんな助けでも大歓迎です。

私のコードはこれらのケースに失敗します:

私の出力は「名前」列と同じですが、正しく再帰していません。

Answer 1

else if ( root.left == null && root.right == null) {
                root.left = new IntTreeNode(0);
                root.right = new IntTreeNode(0);
                lvl++;

これを呼び出した後、それらの新しいノードは決して完成されないので、それらの高さがツリーの高さよりも小さい場合、それらを完成させるためにここに条件を追加する必要があります

else if ( root.left == null && root.right == null) {
                root.left = new IntTreeNode(0);
                root.right = new IntTreeNode(0);
                lvl++;
if(level <height (root)
makePerfect(root.left, lvl +1);
makePerfect(root.left, lvl +1);

Answer 2

これは、将来の参照のための正しい解決策です。

public void makePerfect() {
    int target = height(overallRoot);
    overallRoot = makePerfect(overallRoot,target, 1);
}

private IntTreeNode makePerfect(IntTreeNode root, int target,int lvl) {

    if(root != null) {
        if( lvl < target) {
            if(root.left == null && root.right != null) {
                root.left = new IntTreeNode(0);
                root.left = makePerfect(root.left,target, lvl + 1);
                root.right = makePerfect(root.right,target, lvl +1);
            }if(root.right == null && root.left != null) {
                root.right = new IntTreeNode(0);
                root.right = makePerfect(root.right,target,lvl +1);
                root.left =makePerfect(root.left,target, lvl +1);
            }else if ( root.left == null && root.right == null) {
                root.left = new IntTreeNode(0);
                root.right = new IntTreeNode(0);
                lvl++;
                if(lvl< target) {
                    makePerfect(root.left,target, lvl +1);
                    makePerfect(root.right, target, lvl +1);
                }
            }else {
            root.left = makePerfect(root.left, target,lvl +1);
            root.right = makePerfect(root.right,target, lvl +1);
            }
        }
    }
    return root;
}

Answer 3

またははるかにエレガントなソリューション:

public void makePerfect() {
    overallRoot = makePerfect(overallRoot, 1);
}

private IntTreeNode makePerfect(IntTreeNode root, int level) {
    if (level <= height()) {
        if (root == null) {
            root = new IntTreeNode(0);
        }
        root.left = makePerfect(root.left, level + 1);
        root.right = makePerfect(root.right, level + 1);
    }
    return root;
}