如何计算二叉树的高度

在计算机科学领域中，数据结构如二叉树是常用的数据组织形式之一。二叉树是由节点构成的有序非线性结构，在许多应用场景中有着广泛的应用，例如搜索引擎、数据库索引以及表达式求值等。为了更好地理解和分析二叉树，我们需要掌握一些基本的操作，其中包括计算二叉树的高度。

什么是二叉树的高度

在计算机科学术语中，一个节点的“高度”是指从该节点到最远叶子节点之间的最长简单路径边数。对于一棵空树来说，其高度定义为-1；若根结点无子节点，则其高度为0。

计算二叉树高度的方法

递归法

计算二叉树的高度通常使用递归法来实现，因为它能有效地利用了“子问题”的性质。具体步骤如下：

1. 终止条件：对于空树或叶子结点（无子节点），返回高度0。
2. 递归调用：分别求出左子树和右子树的高度。
3. 计算当前根节点的总高度：在左右子树高度的基础上加一，即为当前根节点的高度。

下面是一个简单的Python代码示例：

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def height(node):
    # 空树高度为-1，叶子节点高度为0
    if node is None:
        return -1
    else:
        # 递归计算左右子树的最大深度
        left_height = height(node.left)
        right_height = height(node.right)
        
        # 当前节点的高度即为其左右子树中较高的那一边再加一
        return max(left_height, right_height) + 1

# 创建一个简单的二叉树：       1
#                   /   \
#                  2     3
#                 / 
#                4  
tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)

print(height(tree)) # 输出5

非递归法

非递归方法通常通过广度优先搜索（BFS）来实现，但这种方法在实际使用中可能不如递归高效。另一种更常见的非递归方法是利用深度优先搜索（DFS），例如后序遍历。

def height_non_recursive(root):
    if root is None:
        return -1

    stack, depth = [(root, 0)], 0
    
    while stack:
        node, curr_depth = stack.pop()
        
        # 更新最大深度
        depth = max(depth, curr_depth)
        
        if node.left:
            stack.append((node.left, curr_depth + 1))
        if node.right:
            stack.append((node.right, curr_depth + 1))

    return depth

print(height_non_recursive(tree)) # 输出5

小结

通过上述讨论，我们可以看到计算二叉树高度的问题可以通过简单的递归方法或者非递归方法来解决。递归法简洁且易于理解，适用于大多数情况；而非递归法则能提供更多的灵活性和控制能力。无论是哪种方法，在实际应用中选择最合适的方式非常重要。