2

I am suppose to write a method makePerfect that could be added to the IntTree class. The method should add nodes until the binary tree is a "perfect" tree. A perfect binary tree is one where all leaves are at the same level. Another way of thinking of it is that you are adding dummy nodes to the tree until every path from the root to a leaf is the same length. A perfect tree's shape is exactly triangular and every branch node has exactly two children. Each node you add to the tree should store the value 0.

An example of before and after calls : enter image description here

my code works for these cases:

enter image description here

but fails others. With this method, there is a helper method that is included that we may only call once.

// 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));
    }
}

What cases am I not testing for ? Been stuck on this for a while, any help would be greatly appreciated.

My code fails these cases: enter image description here

My output is the same as the "name" column, it is not recursing correctly.

4

4 回答 4

3 
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);
于 2013-06-10T15:07:06.147 回答
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;
}
于 2013-06-10T15:16:50.037 回答
1

这是相当可疑的：

 if( lvl < height(root) )

您可能不应该在递归中计算高度，而是将高度作为参数传递。现在你只计算每次递归的高度，所以它会搞砸，因为你可能打算在这里做的是检查级别是否等于整个树的高度，而不是它是否等于高度以当前节点为根的子树。

于 2013-06-10T15:00:51.803 回答
0

或更优雅的解决方案：

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;
}
于 2016-03-01T12:31:24.787 回答