查找二叉树中大于x的节点数 [英] find the number of nodes in a binary tree greater than x
本文介绍了查找二叉树中大于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屋!
查看全文