二叉树进阶：如何计算仅包含偶数层叶子节点的树高度

2026-02-09 01:24:31 0条评论 1次阅读 0人点赞

在日常的算法学习或面试中，计算二叉树的高度（或深度）是最基础的问题之一。通常，我们关注的是从根节点到最远叶子节点的最长路径。但是，作为开发者，我们经常需要处理带有特定约束条件的变体问题。今天，我们将深入探讨一个非常有意思的进阶问题：如何计算一棵二叉树的高度，前提是我们只将位于“偶数层”的叶子节点视为有效的终点。

问题描述

首先，我们需要明确几个关键定义，这为我们后续的编程逻辑打下基础：

  • 树的层： 假设根节点位于第 1 层（奇数层）。它的子节点在第 2 层（偶数层），以此类推。
  • 有效叶子节点： 一个节点如果没有左子节点且没有右子节点，并且它所在的层数是偶数，那么它就是一个“有效叶子节点”。
  • 目标高度： 我们需要计算的是，从根节点出发，到达任意一个有效叶子节点的最长路径上的节点数（或者边数，取决于具体定义，本例中我们通常指路径上的节点计数逻辑）。

如果在某条路径上，所有的叶子节点都位于奇数层，那么这条路径对于我们的计算来说就是“无效”的，不应计入高度。

图示化理解

为了让你更直观地理解这一点，让我们想象一棵简单的二叉树：

  • 根节点 (1) – 第 1 层 (奇数)

* 左节点 (2) – 第 2 层 (偶数)

* 左叶子 (4) – 第 3 层 (奇数，无效)

* 右叶子 (5) – 第 3 层 (奇数，无效)

* 右节点 (3) – 第 2 层 (偶数)

* 这是一个叶子节点！因为它没有子节点，且位于第 2 层（偶数），所以它是一个有效叶子节点。

在这个例子中，虽然根节点通过左子树 (1 -> 2 -> 4) 可以到达更深的深度，但因为 4 是奇数层叶子，我们忽略它。我们的有效路径是 1 -> 3。因此，这棵树的目标高度是 2。

解题思路解析

解决这个问题，我们需要对标准的递归算法进行一些巧妙的修改。普通的深度优先搜索（DFS）只是简单地寻找最深的叶子，而我们需要在搜索过程中“过滤”掉不符合条件的路径。

我们可以将这个大问题拆解为以下几个步骤：

#### 1. 传递层级状态

在递归遍历树时，我们需要知道当前节点处于哪一层。为了做到这一点，我们可以给递归函数传递一个布尔标志位 isEven。

  • 初始时，根节点在第 1 层（奇数），所以传入 false（代表非偶数）。
  • 当递归调用进入子节点时，层级加 1，奇偶性翻转。我们将 !isEven 传递给下一级。

#### 2. 识别有效叶子

在递归的“基准情形”（Base Case）中，我们检查当前节点是否为叶子节点（即左右子节点均为空）：

  • 如果是叶子节点：我们检查 isEven 标志。

* 如果 INLINECODEd63aea55 为 INLINECODEf356d818（说明当前在偶数层），返回 1，表示这里有一个有效的终点，路径长度 +1。

* 如果 INLINECODE7b81260e 为 INLINECODEd469bdd2（说明当前在奇数层），返回 0，表示虽然这是叶子，但它不符合条件，不能贡献高度。

  • 如果是空节点：返回 0。

#### 3. 处理递归结果

这是最关键的一步。对于当前的非叶子节点，我们先分别计算出左右子树的结果（INLINECODE1360eab3 和 INLINECODEda7e45fb）。

  • 情况 A：死路一条

如果 INLINECODE54e18fb5 且 INLINECODE27592202，这意味着左右子树中都没有找到任何有效的偶数层叶子节点。那么，对于当前节点的父节点来说，当前节点这条路径也是无效的。因此，我们返回 0。

  • 情况 B：找到有效路径

如果 INLINECODE5f110d07 或 INLINECODEaa695863 中至少有一个不为 0，说明在下方存在有效的叶子节点。我们需要取 max(left, right)，然后加上当前节点本身（+1），作为返回给上一层的结果。

深入代码实现

让我们把上述逻辑转化为实际的代码。为了确保你能在任何环境下使用，我将提供 C++、Java 和 Python 三种语言的实现，并为关键部分添加详细的中文注释。

#### C++ 实现

/* 
   C++ 程序：计算仅考虑偶数层叶子节点时的二叉树高度
   编译环境：C++11 或更高版本
*/
#include 
#include  // 用于 std::max
using namespace std;

/* 二叉树节点定义 */
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

/*
   核心递归工具函数
   root: 当前节点指针
   isEven: 布尔值，表示当前节点是否位于偶数层
*/
int heightOfTreeUtil(Node* root, bool isEven) {
    // 基准情形：如果节点为空，高度贡献为 0
    if (!root)
        return 0;

    // 检查是否为叶子节点（左右子节点均为空）
    if (!root->left && !root->right) {
        // 只有当该叶子节点位于偶数层时，才计入高度
        if (isEven)
            return 1;
        else
            return 0;
    }

    /*
       递归步骤：
       计算左右子树的高度。
       注意：传递 !isEven，因为子节点的层级相对于当前节点发生了奇偶翻转。
    */
    int left = heightOfTreeUtil(root->left, !isEven);
    int right = heightOfTreeUtil(root->right, !isEven);

    /*
       关键逻辑：判断路径有效性
       如果左右子树都返回 0，说明下方没有通往偶数层叶子节点的路径。
       这意味着对于父节点而言，当前分支是“死路”，返回 0。
    */
    if (left == 0 && right == 0)
        return 0;

    /*
       如果至少有一个子树返回了非零值，说明存在有效路径。
       我们取较长的那条路径，并加上当前节点自身的高度贡献 (+1)。
    */
    return (1 + max(left, right));
}

/* 辅助函数：创建新节点 */
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}

/* 包装函数：用户调用的入口 */
int heightOfTree(Node* root) {
    // 根节点定义为第 1 层（奇数），所以初始传入 false
    return heightOfTreeUtil(root, false);
}

/* 主函数：测试代码 */
int main() {
    /*
       构建用于测试的二叉树结构：
              1       (Level 1, Odd)
            /   \
           2     3    (Level 2, Even)
          / \
         4   5        (Level 3, Odd)
            /
           6           (Level 4, Even - 有效叶子)
    */
    struct Node* root = newNode(1);

    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    // 添加一个深层偶数叶子节点 6
    root->left->right->left = newNode(6);

    // 计算并输出结果
    // 路径分析：
    // 1->2->4 (叶子在奇数层，无效)
    // 1->2->5->6 (叶子6在偶数层，长度为4，有效)
    // 1->3 (叶子在偶数层，长度为2，有效)
    // 最大高度为 4
    cout << "Height of tree is " << heightOfTree(root) << endl;
    return 0;
}

#### Java 实现

/* 
   Java 程序：计算仅考虑偶数层叶子节点时的二叉树高度 
*/
class BinaryTreeHeight {

    /* 二叉树节点定义 */
    static class Node { 
        int data; 
        Node left; 
        Node right; 
    }

    /*
       核心递归工具函数
       root: 当前节点
       isEven: 当前节点是否处于偶数层
    */
    static int heightOfTreeUtil(Node root, boolean isEven) { 
        // 基准情形：空节点
        if (root == null) 
            return 0; 

        // 检查是否为叶子节点
        if (root.left == null && root.right == null) { 
            // 仅当位于偶数层时计数
            if (isEven == true) 
                return 1; 
            else
                return 0; 
        } 

        // 递归计算子树，层级翻转
        int left = heightOfTreeUtil(root.left, !isEven); 
        int right = heightOfTreeUtil(root.right, !isEven); 

        /*
           如果两边都是死路，则当前路径无效
        */
        if (left == 0 && right == 0) 
            return 0; 

        // 返回有效路径的最大值加当前节点
        return (1 + Math.max(left, right)); 
    } 

    /* 辅助函数：创建新节点 */
    static Node newNode(int data) { 
        Node node = new Node(); 
        node.data = data; 
        node.left = null; 
        node.right = null; 
        return node; 
    } 

    /* 包装函数 */
    static int heightOfTree(Node root) { 
        // 根节点为第 1 层（奇数），传入 false
        return heightOfTreeUtil(root, false); 
    } 

    /* 主函数：测试逻辑 */
    public static void main(String[] args) { 
        /*
           构建树：
              1
            /   \
           2     3
          / \
         4   5
            /
           6
        */
        Node root = newNode(1); 
        root.left = newNode(2); 
        root.right = newNode(3); 
        root.left.left = newNode(4); 
        root.left.right = newNode(5); 
        root.left.right.left = newNode(6); 
        
        // 输出预期: 4 (路径 1-2-5-6)
        System.out.println("Height of tree is " + heightOfTree(root)); 
    }
}

#### Python3 实现

# Python3 程序：计算仅考虑偶数层叶子节点时的二叉树高度

class newNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def heightOfTreeUtil(root, isEven):
    # 基准情形：空节点
    if (not root):
        return 0

    # 检查是否为叶子节点
    if (not root.left and not root.right):
        # 仅在偶数层计数
        if (isEven):
            return 1
        else:
            return 0

    # 递归步骤：层级翻转
    left = heightOfTreeUtil(root.left, not isEven)
    right = heightOfTreeUtil(root.right, not isEven)

    # 死路检测
    if (left == 0 and right == 0):
        return 0

    # 返回最大路径加当前节点
    return (1 + max(left, right))

def heightOfTree(root):
    # 根节点为第 1 层（奇数），传入 False
    return heightOfTreeUtil(root, False)

# Driver Code
if __name__ == ‘__main__‘:
    # 构建测试树
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
    root.left.right.left = newNode(6)
    
    print("Height of tree is", heightOfTree(root))

算法复杂度与性能分析

在结束之前，让我们简单分析一下这个算法的性能。

  • 时间复杂度：O(N)

这里的 N 是二叉树中的节点总数。正如我们看到的，算法本质上是对树进行了一次遍历（类似于后序遍历）。每个节点只被访问了一次，并且在每个节点上的操作（比较、加法、逻辑判断）都是常数时间的。因此，时间复杂度与节点数成线性关系。

  • 空间复杂度：O(H)

这里 H 指的是树的高度。空间消耗主要来自于递归调用栈。在最坏的情况下（树退化为一个链表），递归深度将等于节点数 N。但在平衡的二叉树中，深度为 log N。考虑到我们存储的 isEven 布尔值在每次递归中只占用常数空间，整体空间复杂度由树的形态决定。

常见误区与最佳实践

在处理这类问题时，初学者容易犯几个错误，我们这里总结一下，希望能帮你避开坑：

  • 忽略“路径必须有效”的前提：如果你只是简单地检查每个叶子是否在偶数层并记录最大深度，你可能会计算出不连通的路径。例如，你可能会记录下一个很深的偶数叶子，但忽略了根节点根本无法通过合法的偶数层路径到达那里（虽然在这个特定定义下，叶子总是有父节点的，但在“特定层节点作为路径一部分”的类似问题中，这个逻辑至关重要）。在我们的逻辑中，if (left == 0 && right == 0) return 0; 这一行是关键，它确保了连续性。
  • 混淆根节点的层数：有些定义从 0 开始计数，有些从 1 开始。在这个特定问题中，我们假设根节点是第 1 层。如果题目改为根节点是第 0 层（偶数），那么初始传入的参数就需要变成 true。务必根据题目的具体定义调整初始值。
  • 返回值的选择：我们在递归中返回路径的节点数（包括当前节点）。如果你习惯于计算“边数”，记得在最终返回时可能需要减 1，或者在逻辑中保持一致。对于本题，我们统一使用节点计数来表示高度。

实际应用场景

虽然这看起来像是一个纯粹的算法谜题，但类似的逻辑在实际工程中非常有用：

  • 网络协议路由：假设节点是路由器，我们只想计算经过“特定类型”（偶数层）的中继节点到达终端的路径代价。
  • 游戏开发中的AI寻路：在某些网格地图中，某些格子（奇数层）可能被视为“不可停留”或“高风险”区域，我们计算高度或代价时可能会排除以这些区域为终点的路径。
  • XML/HTML DOM树分析：在解析文档树时，我们可能只关心特定深度级别的标签（例如只关注偶数深度的 div 标签）及其结构高度。

总结

通过这篇文章，我们不仅解决了“计算仅考虑偶数层叶子节点的树高度”这个问题，更重要的是，我们学习了一种处理带约束条件的树遍历的思维模式。

关键在于：

  • 传递状态：通过参数（如 isEven）将层级信息传递给递归深处的节点。
  • 定义有效返回：明确什么情况下节点对结果有贡献（返回非零值），什么情况下没有贡献（返回 0）。
  • 剪枝无效路径：利用子节点的返回值来判断当前分支是否有效，从而“剪掉”那些不符合条件的路径。

希望这种分析问题的思路能帮助你在面对更多复杂的树形结构问题时游刃有余。你可以尝试修改上述代码，比如改为“只考虑奇数层叶子”或者“计算所有偶数层节点的数量”，来巩固你的理解。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/37904.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年