递归统计二叉搜索树指定层级节点数报错排查

你的代码存在4个核心问题，是导致编译报错、运行异常的原因：

• 方法调用主体错误：getLeft()、getRight()是Node类的成员方法，你当前将countAtLevel写在BST独立类中，this指向BST实例本身，实例不存在这两个方法，直接触发cannot find symbol method: getLeft()编译错误。
• 变量名不匹配：方法入参名为l，终止条件判断时却使用了未定义的变量level，会触发变量找不到的编译错误。
• 空指针隐患：递归时直接调用getLeft().countAtLevel()，没有提前判断左、右子节点是否为null，子节点为空时调用方法会直接抛出空指针异常。
• 递归逻辑分层错误：客户端是调用BST实例的countAtLevel(l)方法，但递归逻辑需要基于节点逐层遍历，不能直接在BST类的方法中递归调用自身，需要拆分公开调用入口和节点层面的递归实现。

另外你给出的Node类原始代码存在语法错误：getRight()方法的返回语句多了一个多余的右括号，需要先修正。

正确实现代码 #

1. 修正语法后的Node类，内置节点层面的递归统计逻辑 #

class Node {
    String data;
    Node rChild;
    Node lChild;

    public Node getLeft() {
        return this.lChild;
    }

    public Node getRight() {
        // 原代码此处多了一个右括号，已修正
        return this.rChild;
    }

    public String getData() {
        return this.data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public void setLeft(Node left) {
        this.lChild = left;
    }

    public void setRight(Node right) {
        this.rChild = right;
    }

    // 节点递归统计指定层级节点数
    public int countAtLevel(int l) {
        // 递归到目标层级，当前节点计数1
        if (l == 0) {
            return 1;
        }
        int total = 0;
        // 左子节点非空时才递归下探，避免空指针
        if (this.lChild != null) {
            total += this.lChild.countAtLevel(l - 1);
        }
        // 右子节点非空时才递归下探
        if (this.rChild != null) {
            total += this.rChild.countAtLevel(l - 1);
        }
        return total;
    }
}

2. BST独立类，提供客户端调用的公开方法 #

public class BinarySearchTree {
    private Node root;

    // 客户端调用入口
    public int countAtLevel(int l) {
        // 空树、非法层级参数直接返回0
        if (root == null || l < 0) {
            return 0;
        }
        // 从根节点开始递归统计
        return root.countAtLevel(l);
    }

    // 省略BST原有的插入、删除、遍历等其他方法
}

结果验证 #

针对你给出的示例二叉树：

3
     / \
    2   5
   /   / \
  1   4   7

调用方法的返回值完全符合预期：

• countAtLevel(0)：根节点3为第0层，返回1
• countAtLevel(1)：第1层节点为2、5，返回2
• countAtLevel(2)：第2层节点为1、4、7，返回3

内容的提问来源于stack exchange，提问作者darkren12