java - 二叉树 : Node frequency count for 0, 1 或 2 个 child

Question

我有一个任务:

You’re given the root node of a binary tree T. We distinguish between 3 types of nodes in T: nodes with 0 children, nodes with 1 child, and nodes with 2 children. Determine, for each type, the number of nodes in T. Return your result as an integer array of length 3.

我得到了一个 Java 文件，它为该算法生成随机测试用例。

我只能创建一个函数来完成所有这些。我不允许将任何其他参数传递到下面的方法中。我也不允许在我创建的函数之外进行任何其他修改。

在文件中，已经插入了一个基本案例。有人告诉我使用递归按后序遍历树。

我知道我的代码目前存在的问题。但我不知道如何修复它们。

我目前的代码如下:

private static int[] problem1(Node root) {

    int[] arr = new int[3];

    if (root == null) {
        return new int[] {
            -1, // nodes with 0 children
            -1, // nodes with 1 child
            -1 // nodes with 2 children
        };
    }
    //problem1(root.left);
    //problem1(root.right);

    if (root.left != null && root.right != null) {
        arr[2]++;
        problem1(root.left);
        problem1(root.right);
    } else if (root.left != null && root.right == null) {
        arr[1]++;
        problem1(root.left);
    } else if (root.left == null && root.right != null) {
        arr[1]++;
        problem1(root.right);
    } else {
        arr[0]++;
    }
    return arr;
}

Node 类定义为:

static class Node {
            public int value;
            public Node left;
            public Node right;
        }

Answer 1

class Playground {
    public static void main(String[ ] args) {
        Node root = new Node(1, new Node(2, null, null), new Node(3, null, null));
        int[] counts = problem1(root);
        System.out.println(counts[0]); // 2 node(s) with 0 children
        System.out.println(counts[1]); // 0 node(s) with 1 children
        System.out.println(counts[2]); // 1 node(s) with 2 children
    }

    // recursively count number of childs for each root/node. Post-order 
    // traversing means both left and right node will be traversed before
    // any computations.
    public static int[] problem1(Node root) {
        // always need a base-case to stop recursive call.
        if(root == null) {
            return new int[]{0,0,0};
        }

        // post-order traversing
        int[] leftChildCounts = problem1(root.left);
        int[] rightChildCounts = problem1(root.right);

        int [] counts = new int[]{0,0,0};
        counts[0] = leftChildCounts[0] + rightChildCounts[0];
        counts[1] = leftChildCounts[1] + rightChildCounts[1];
        counts[2] = leftChildCounts[2] + rightChildCounts[2];

        if(root.left == null && root.right == null) {
            counts[0]++;
        } else if(root.left != null && root.right != null) {
            counts[2]++;
        } else {
            counts[1]++;
        }        
        return counts;
    }
}

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value, Node left, Node right) {
        this.value = 0; 
        this.left = left;
        this.right = right;
    }       
}