java - 如何为这个删除任何奇数节点及其子节点的递归函数编写基本情况？

Question

应该发生的事情是:删除所有具有奇数根的子树(如果节点是奇数，则删除它及其后代)如果一个节点有一个奇数键，则该节点是奇数如果根是奇数，那么你最终应该得到空树

我的代码如下。它基本上在所有测试中都失败了。特别是两个是:“失败的removeOddSubtrees(41 21 61 11 31):期望()实际(41)”“删除OddSubtrees失败(100 40 20 61 11 31 51 71 140 120 161 111 131 151 171):预期(100 40 140 20 120)实际(100 40 140 20 61 120 161 11 31 111) 131)”

问题限制: - 不要更改 Node 类。 - 不要更改任何函数的第一行:名称、参数、类型。

private Node root;
private static class Node {
    public final int key;
    public Node left, right;
    public Node(int key) { this.key = key; }
}

public void removeOddSubtrees() {
   if (root == null) {
     return;
   }
   removeOddSubtrees(root);
 }

private void removeOddSubtrees(Node root){
        if(root != null){
        removeOddSubtrees(root.left);
        removeOddSubtrees(root.right);
        if(root.key % 2 != 0){
            root.right = null;
            root.left = null;
            root = null;
        }else{
            return;
        }
    }
    }

Answer 1

您的逻辑应该是，如果在递归中的任何节点，左或右子节点为奇数，则不要递归并分配 null，否则进行递归调用。

public Node removeOddSubtrees() {
    // if the root is already null or odd, then just return null for the entire tree
    if (root == null) return null;

    if (root.key % 2 != 0) {
        root = null;
        return root;
    }

    removeOddSubtrees(root);

    return root;
}

private void removeOddSubstrees(Node root) {
    if (root.left != null) {
        if (root.left.key % 2 != 0) {
            root.left = null;
        }
        else {
            removeOddSubstrees(node.left);
        }
    }

    if (root.right != null) {
        if (root.right.key % 2 != 0) {
            root.right = null;
        }
        else {
            removeOddSubstrees(node.right);
        }
    }
}