计算BST中的剩余节点数 [英] Count number of left nodes in BST

问题描述

鉴于BST，我需要找到树的左节点数.

Given a BST, I am required to find the number of left nodes of the tree.

示例:`

          +---+
          | 3 |
          +---+
         /     \
     +---+     +---+
     | 5 |     | 2 |
     +---+     +---+
    /         /     \
+---+     +---+     +---+
| 1 |     | 4 |     | 6 |
+---+     +---+     +---+
         /
     +---+
     | 7 |
     +---+`

答案应该是4，因为(5、1、4、7)是树的所有左节点.

The answer should be 4, as (5, 1 , 4, 7) are all left nodes of the tree.

我想做的是:

public int countLeftNodes() {
    return countLeftNodes(overallRoot, 0);
}

private int countLeftNodes(IntTreeNode overallRoot, int count) {
    if (overallRoot != null) {
        count += countLeftNodes(overallRoot.left, count++);    
        count = countLeftNodes(overallRoot.right, count);
    }
    return count;
}

我知道这是错误的，但我不知道为什么.有人可以解释原因，也可以帮助我给出答案.

I know it is wrong, but I don't know why. Could someone explain why, and also help me with the answer.

推荐答案

第二个递归分支将覆盖第一个递归分支的值.另外，您还应该为左根添加1.

The second recursion branch overwrites the value from the first. Also you should add 1 for the left root.

类似的东西:

private int countLeftNodes(IntTreeNode node) {
    int count = 0;
    if (node.left != null) 
        count += 1 + countLeftNodes(node.left);    

    if (node.right != null)
        count += countLeftNodes(node.right);


    return count;
}

这篇关于计算BST中的剩余节点数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！