时间戳

首页 > 解决方案 > 根据子节点数确定二叉树中的节点数

java - 根据子节点数确定二叉树中的节点数

问题描述

您将获得二叉树T的根节点。我们区分T中的三种类型的节点：具有 0 个子节点（即叶子）的节点、具有 1 个子节点的节点和具有两个子节点的节点。为每种类型确定T中的节点总数。将结果作为长度为 3 的整数数组返回。

输出应该是一个数组，其中包含上述所有类型的节点的计数。

这就是我所拥有的，但是当我运行它时它没有通过我的教练的测试：

private static int[] problem1(Node root){

     int[] nodeCount = new int[]{0,0,0};

     // BASE CASE
     if (root == null) {

        // Implement me!
        return new int[] {
           -1, // nodes with 0 children
           -1, // nodes with 1 child
           -1  // nodes with 2 children
        };

     }

     // RECURSIVE CALL
     int[] leftChild = problem1(root.left);
     int[] rightChild = problem1(root.right);

     nodeCount[0] = leftChild[0] + rightChild[0];
     nodeCount[1] = leftChild[1] + rightChild[1];
     nodeCount[2] = leftChild[2] + rightChild[2];

     if(root.left != null && root.right != null) {

        nodeCount[2]++;
        problem1(root.left);
        problem1(root.right);

     }else if(root.left != null && root.right == null) {

        nodeCount[1]++;
        problem1(root.left);

     }else if(root.left == null && root.right != null) {

        nodeCount[1]++;
        problem1(root.right);

     }else {

        nodeCount[0]++;
     }

     return nodeCount;
}

标签： javabinary-treenodes

解决方案

我正在编写粗略的代码，请检查它是否解决了您的问题：

    HashMap<Integer, Integer> count = new HashMap<>();

    // For now, 0 key having a count of leaf nodes, 1 key count of nodes having a single child, 2 for both 
    // Use inorder, pre or post to traverse the tree... use countNodes to get count
    // I have used hashmap to keep count, you can take an array as well.

   public void inorder(TreeNode root){
       if(root == null) return;
       inorder(root.left);
       countNodes(root);
      inorder(root.right);
    }

  public void countNodes(TreeNode root){
       if(root == null) return;
       else if(root.left != null && root.right != null){
         count.put(2, 1 + count.getOrDefault(2,0));
       } 
      else if(root.left == null && root.right == null){
         count.put(0, 1 + count.getOrDefault(0,0));
       } 
      else{
         count.put(1, 1 + count.getOrDefault(1,0));
      } 
    }

推荐阅读