如何正确遍历二叉树计算根到最远叶节点的树高

当前实现仅遍历从根节点出发的最左侧连续通路、最右侧连续通路，完全没有处理子树的内部分支结构，只要最长路径出现在左右子树的内部分支上，就会被遗漏，自然无法算出正确高度。

二叉树高度本身是递归定义的：以任意节点为根的子树高度，等于其左子树高度、右子树高度的最大值，再加1（对应当前节点到子节点的边/当前节点层，可根据计数规则微调基准值）。需要对每个节点的左右子树都执行相同的高度计算逻辑，而非仅沿着单条链路向下遍历。

递归实现（和定义完全匹配，代码最简洁） #

基准值规则：如果高度定义为「根节点到最远叶子节点的路径边数」，空节点返回-1；如果定义为「路径上的节点总数」，空节点返回0即可。以下代码按你需要的路径长度（边数）规则实现：

static int getHeight(Node root){
    // 递归终止条件：遍历到空位置，没有可计数的边
    if (root == null) {
        return -1;
    }
    // 分别递归计算当前节点左、右子树的高度
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    // 当前节点高度 = 左右子树最大高度 + 当前节点到子节点的1条边
    return Math.max(leftHeight, rightHeight) + 1;
}

如果需要按节点数统计高度，仅需把空节点的返回值改为0，单根节点的树返回值即为1，符合计数逻辑。

迭代实现（避免递归栈溢出的可选方案） #

可以用层序遍历（广度优先搜索）实现：每遍历完一整层节点，高度计数加1，直到遍历完所有层级，天然能覆盖所有内部叶子节点，不会出现遗漏：

import java.util.LinkedList;
import java.util.Queue;

static int getHeight(Node root){
    if (root == null) {
        return -1; // 节点数计数场景下改返回0
    }
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    int height = -1; // 节点数计数场景下初始值设为0
    while (!queue.isEmpty()) {
        int levelNodeCount = queue.size();
        // 遍历当前层的所有节点，把下一层子节点全部入队
        for (int i = 0; i < levelNodeCount; i++) {
            Node current = queue.poll();
            if (current.left != null) {
                queue.offer(current.left);
            }
            if (current.right != null) {
                queue.offer(current.right);
            }
        }
        // 整层遍历完成，高度加1
        height++;
    }
    return height;
}

两种实现都会遍历树中的全部节点，不会漏掉任何内部叶子节点，计算过程会自动对比所有根到叶子的路径长度，最终返回正确的最大高度值。

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