查找二叉树中大于x的节点数 [英] find the number of nodes in a binary tree greater than x

问题描述

public static int nodesGreaterThanX(BinaryTreeNode<Integer> root,int k,int count)
{
    if(root==null)
        return 0;
    if(root.data>k){
        System.out.print(root.data + " ");
        count++;
    }
    int countLeft = nodesGreaterThanX(root.left, k,count);
    int countRight = nodesGreaterThanX(root.right, k,count);

    return count + countLeft + countRight;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    BinaryTreeNode<Integer> root = takeInput();
    int count = nodesGreaterThanX(root, 2,0);
    System.out.println();
    System.out.println(count);
}

我希望获得大于x的节点数(在本例中为2)，但我的答案不正确，并且我无法在程序中找到问题 如果不需要，请不要更改逻辑，并告诉我哪里出错了。

推荐答案

如果您从根向下遍历树，则根本不需要向下传播‘count’--这样做会导致对节点的重复计数，因为它们对count、countLeft和countRight都有贡献，因为您在将count传递给nodesGreaterThanX之前对count递增。

public static int nodesGreaterThanX(BinaryTreeNode<Integer> node, int k) {
  if (node == null) {
    return 0;
  }

  int countLeft = nodesGreaterThanX(node.left, k);
  int countRight = nodesGreaterThanX(node.right, k);

  return (node.data > k ? 1 : 0) + countLeft + countRight;
}

这篇关于查找二叉树中大于x的节点数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！