我的JavaScript二叉树CountHeight函数存在什么问题？

嘿，这个问题我碰到好多次了！先帮你理清楚：你说的那棵树结构应该是这样的吧？

10
   /  \
  4   15
 /
8

按节点层数算的话，高度确实是3，但你的函数返回2，十有八九是递归逻辑的终止条件或者计算步骤写错了。

最常见的错误原因 #

很多新手写高度计算函数时，容易漏掉当前节点的层数，比如写出这样的错误代码：

def wrong_height(root):
    if not root:
        return 0
    left = wrong_height(root.left)
    right = wrong_height(root.right)
    return max(left, right)

这个函数算出来的是边数（从根到叶子的路径上的边的数量），所以你的树会返回2，但你要的是节点数的高度，就得在取最大值后加1。

正确的实现代码 #

如果是按节点数计算高度，正确的递归写法应该是这样（拿Python举例，其他语言逻辑一样）：

def get_tree_height(root):
    # 空树的高度定义为0
    if not root:
        return 0
    # 递归计算左右子树的高度
    left_height = get_tree_height(root.left)
    right_height = get_tree_height(root.right)
    # 当前节点的高度 = 左右子树的最大高度 + 自身这一层
    return max(left_height, right_height) + 1

用你的树测试一下：

• 节点8的左右子节点都是空，返回 max(0,0)+1=1
• 节点4的右子节点为空，左子节点高度是1，返回 max(1,0)+1=2
• 节点15的左右子节点为空，返回1
• 根节点10取左右子树的最大高度2，加1后得到3，完美符合你的预期！

额外排查点 #

如果换了正确代码还是不对，那得检查你构建树的逻辑了——是不是节点8没有正确挂载到节点4的left或right属性上？比如不小心把8挂成了10的另一个子节点，那树的高度就真的是2了。

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