二叉树高度实现存疑：是否需调整叶子节点的返回值？

嘿，这个问题的核心其实是二叉树「高度」的两种不同定义，不是原代码有“不必要的1”，咱们来理清楚：

首先，行业里关于二叉树高度有两种主流约定：

• 定义1：高度为节点的层数（从根到该节点的节点总数）。比如空树高度为0，单个叶子节点高度为1，根节点带一个子节点的树高度为2。
• 定义2：高度为从节点到叶子的最长边数。比如空树高度为0，单个叶子节点高度为0，根节点带一个子节点的树高度为1。

原代码的逻辑 #

你查到的常见实现对应的是「定义1」，代码如下：

public int height(BinaryNode t) { 
    if (t == null) { 
        return 0; 
    } else { 
        return 1 + Math.max(height(t.left), height(t.right)); 
    } 
}

这个实现里，叶子节点会返回1，符合“节点层数”的高度定义，这是很多教材、数据结构库默认采用的方式，比如Java中不少树结构的高度计算都遵循这个约定。

你修改后的代码逻辑 #

你的修改版对应的是「定义2」，代码如下：

public int height(BinaryNode t) { 
    if (t == null) { 
        return 0; 
    } else if (t.left == null && t.right == null) { 
        return 0; 
    } else { 
        return 1 + Math.max(height(t.left), height(t.right)); 
    } 
}

这里你特意给叶子节点返回0，贴合“边数高度”的定义，这种实现也完全合理——只要你的业务场景是按边数来计算高度，这个写法没问题。

更简洁的「边数高度」实现 #

其实不需要单独判断叶子节点，调整空树的返回值就能更简洁地实现「定义2」：

public int height(BinaryNode t) {
    if (t == null) {
        return -1; // 空树的边数高度为-1
    }
    return 1 + Math.max(height(t.left), height(t.right));
}

这个写法里，单个叶子节点会返回1 + max(-1, -1) = 0，完美符合边数高度的定义，同时避免了额外的叶子节点判断逻辑。

总结来说：两种实现都没有错，关键看你需要遵循哪种高度定义。如果是按节点层数算，原代码正确；如果是按边数算，你的修改或者上面的简洁写法都可行。

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