计算BST中左节点的数量

Question

给定BST,我需要找到树的左节点数.

示例:`

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

答案应该是4,因为(5,1,4,7)都是树的左节点.

我在想的是:

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;
}

我知道这是错的,但我不知道为什么.有人可以解释原因,并帮助我解决问题.

Answer 1

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

就像是:

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;
}