在数据结构与算法的学习中，二叉树是一种非常重要的结构。理解二叉树的深度和高度是深入掌握二叉树的关键。本篇博客将围绕二叉树的深度与高度展开讨论，详细介绍它们的定义、区别、计算方法以及在实际问题中的应用。

一、基本定义

1. 深度（Depth）

深度是从树的根节点到当前节点所经历的边的数量。换句话说，根节点的深度为0，其子节点的深度为1，依此类推。

2. 高度（Height）

高度是从当前节点到其最远叶子节点所经历的边的数量。叶子节点的高度为0，其父节点的高度为1，依此类推。

3. 树的深度与高度

  • 树的深度是指从根节点到最远叶子节点所经历的边的数量。
  • 树的高度是指根节点的高度，等价于树的深度。

4. 区别

  • 节点的深度描述的是节点距离根节点的远近。
  • 节点的高度描述的是节点距离叶子节点的远近。
  • 树的深度和树的高度在定义上是相同的，通常是从根节点到最远叶子节点的边数。

二、深度与高度的计算

1. 递归计算节点深度

假设我们需要计算二叉树中某个节点的深度，可以采用递归方法：

1
2
3
4
5
6
7
8
9
10
11
12
# 计算节点深度
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def get_depth(node, current_depth=0):
    if node is None:
        return current_depth - 1
    return max(get_depth(node.left, current_depth + 1),
               get_depth(node.right, current_depth + 1))

2. 递归计算节点高度

二叉树的节点高度可以通过递归计算左右子树的高度，然后取最大值加1：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 计算节点高度
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def get_height(node):
    if node is None:
        return -1  # 空节点高度为-1
    left_height = get_height(node.left)
    right_height = get_height(node.right)
    return max(left_height, right_height) + 1

3. 非递归实现树的高度

我们也可以使用层序遍历来计算树的高度。每遍历一层，计数器加1，最终计数器的值就是树的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque

def get_tree_height(root):
    if not root:
        return -1
    queue = deque([root])
    height = -1
    while queue:
        height += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return height

三、深度与高度的应用

1. 判断二叉树是否平衡

平衡二叉树的定义是任意节点的左右子树高度差不超过1。可以通过递归计算左右子树高度并进行比较。

2. 寻找最近公共祖先

在二叉树中，两个节点的最近公共祖先是深度最深的公共节点。通过比较节点的深度，可以逐步向上找到公共祖先。

3. 最长路径计算

二叉树的最长路径（直径）是左右子树高度之和加1。通过递归计算左右子树高度，可以轻松求得。

四、总结

深度与高度是二叉树中两个重要且容易混淆的概念：

  • 深度从根节点向下计算，描述节点距离根节点的远近。
  • 高度从叶子节点向上计算，描述节点距离叶子节点的远近。

理解这两个概念及其计算方法，对于解决二叉树相关问题至关重要。希望本文能帮助你更好地掌握二叉树的深度与高度。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。