JS中无法获取二叉搜索树（BST）深度的问题排查

核心错误点 #

• 递归函数未返回值：getDepth函数在处理非叶子节点（存在左/右子树）的分支中，仅计算了左右子树的深度并打印日志，但没有返回当前节点的深度值。这会导致上层递归调用时得到undefined，进而计算1 + undefined得到NaN，最终出现变量异常。
• 冗余的条件判断：单独判断tree.left === null && tree.right === null返回1是多余的，递归逻辑本身可以覆盖这种情况（左右子树深度都是0，1 + max(0,0) = 1），反而增加了代码复杂度。

修复后的代码 #

修正后的getDepth函数 #

function getDepth(tree) {
    if (tree === null) {
        return 0;
    }
    // 递归计算左右子树深度
    const depthLeft = 1 + getDepth(tree.left);
    const depthRight = 1 + getDepth(tree.right);
    // 返回当前节点的最大深度
    const maxDepth = Math.max(depthLeft, depthRight);
    // 可选日志，用于调试
    console.log(`节点${tree.data}：左深度${depthLeft}，右深度${depthRight}，当前最大深度${maxDepth}`);
    return maxDepth;
}

完整可运行代码 #

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    insert(data) {
        const newNode = new Node(data);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    insertNode(node, newNode) {
        if (newNode.data < node.data) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
}

function getDepth(tree) {
    if (tree === null) {
        return 0;
    }
    const depthLeft = 1 + getDepth(tree.left);
    const depthRight = 1 + getDepth(tree.right);
    const maxDepth = Math.max(depthLeft, depthRight);
    console.log(`节点${tree.data}：左深度${depthLeft}，右深度${depthRight}，当前最大深度${maxDepth}`);
    return maxDepth;
}

function run(arr) {
    const tree = new BinarySearchTree();
    for (const elem of arr) {
        tree.insert(elem);
    }
    const result = getDepth(tree.root);
    console.log(`树的总深度：${result}`);
}

run([12,7,19,5,9,10]);

运行结果说明 #

运行run([12,7,19,5,9,10])后，生成的BST结构为：

12
    /    \
   7      19
  / \
 5   9
      \
       10

修复后的函数会正确返回总深度4（从根节点12到叶子节点10的路径长度）。

内容的提问来源于stack exchange，提问作者no-syntax-cobol