平衡路径计数

题目描述

定义二叉树的平衡路径需同时满足以下 3 个条件：

1. 路径从任意节点出发，仅能向下延伸（只能向左/右子节点，不可向上回溯）。
2. 路径上所有节点的和相加为 0。
3. 路径长度（包含的节点个数）至少为 2。

请实现一个 Python 函数，输入二叉树的根节点（按层序遍历规则构建），返回该树中所有"平衡路径"的总数。

建树规则： 层序遍历列表按「从上到下、从左到右」的顺序构建二叉树，None 表示对应位置无节点。

路径延伸： 从起点出发，仅沿左子节点 OR 右子节点单向向下（单链，不可分叉）。

统计方式： 每个符合条件的单链路径独立计数（即使路径有重叠）。

输入格式

• 一行：二叉树的层序遍历列表（元素为整数或 None，None 表示空节点）

输出格式

• 整数，表示平衡路径的总数

示例

示例 1

输入：

[10, -5, -5, 2, -2, 3, -3]

输出：

0

说明： 无合法路径。所有可能的路径和均不为 0。

示例 2

输入：

[0, 0, None]

输出：

1

说明： 根节点 0 → 左孩子 0，路径和为 0，长度为 2，满足条件。

示例 3

输入：

[1, -1, 2, -2, None, 3, -3]

输出：

2

说明： 两条路径：$1 \to -1$（和为 $1+(-1)=0$）和 $1 \to 2 \to -3$（和为 $1+2+(-3)=0$）。

---

解题思路

第一步：理解问题本质

平衡路径要求：路径和为 0，长度至少为 2，只能向下走。这意味着我们需要枚举所有从任意节点出发、沿子节点向下的路径，检查是否满足条件。

第二步：暴力解法

对每个节点，枚举所有可能的向下路径，计算路径和。时间复杂度 $O(N \cdot H)$，其中 $H$ 是树的高度。对于每个节点作为起点，DFS 遍历所有可能的向下路径。

第三步：最优解法

收集所有节点作为起点，对每个起点使用栈进行 DFS，维护当前路径和与路径长度。当路径长度 $\geq 2$ 且路径和为 0 时，计数加 1。

具体实现：

1. 按层序遍历构建二叉树
2. 层序遍历收集所有节点（作为路径起点）
3. 对每个起点，用栈模拟 DFS，维护 (当前节点, 从起点到当前节点的和, 路径长度)
4. 长度 $\geq 2$ 且和为 0 时，计数

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码152 帧 · 录制输入 [10, -5, -5, 2, -2, 3, -3]

"""
平衡路径计数 - 二叉树 DFS

输入格式：
- 一行：二叉树的层序遍历列表（元素为整数或None）

输出格式：
- 整数，表示平衡路径的总数
"""

import sys
from collections import deque

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

def build_tree(level_order):
    """根据层序遍历列表构建二叉树，返回根节点"""
    if not level_order or level_order[0] is None:
        return None
    root = TreeNode(level_order[0])
    queue = deque([root])
    i = 1
    n = len(level_order)
    while queue and i < n:
        node = queue.popleft()
        # 左孩子
        if i < n and level_order[i] is not None:
            node.left = TreeNode(level_order[i])
            queue.append(node.left)
        i += 1
        # 右孩子
        if i < n and level_order[i] is not None:
            node.right = TreeNode(level_order[i])
            queue.append(node.right)
        i += 1
    return root

def count_balance_paths(root):
    """统计所有平衡路径的个数"""
    if not root:
        return 0
    total = 0
    # 层序遍历收集所有节点（作为路径起点）
    nodes = []
    q = deque([root])
    while q:
        cur = q.popleft()
        nodes.append(cur)
        if cur.left:
            q.append(cur.left)
        if cur.right:
            q.append(cur.right)

    # 对每个起点，向下DFS统计合法路径
    for start in nodes:
        stack = [(start, start.val, 1)]  # (当前节点, 从起点到当前节点的和, 路径长度)
        while stack:
            node, cur_sum, length = stack.pop()
            # 长度>=2且和为0，计数
            if length >= 2 and cur_sum == 0:
                total += 1
            if node.left:
                stack.append((node.left, cur_sum + node.left.val, length + 1))
            if node.right:
                stack.append((node.right, cur_sum + node.right.val, length + 1))
    return total

if __name__ == "__main__":
    line = sys.stdin.readline().strip()
    if not line:
        print(0)
    else:
        level_order = eval(line)
        root = build_tree(level_order)
        result = count_balance_paths(root)
        print(result)

---

示例推演

以样例 3 为例：输入 [1, -1, 2, -2, None, 3, -3]

建树结果：

        1
       / \
     -1   2
     /   / \
   -2   3  -3

收集所有节点作为起点： [1, -1, 2, -2, 3, -3]

起点 1：

• 1 → -1：和 1 + (-1) = 0，长度 2 ✓
• 1 → -1 → -2：和 1 + (-1) + (-2) = -2，不满足
• 1 → 2：和 1 + 2 = 3，不满足
• 1 → 2 → 3：和 1 + 2 + 3 = 6，不满足
• 1 → 2 → -3：和 1 + 2 + (-3) = 0，长度 3 ✓

起点 -1：

• -1 → -2：和 -3，不满足

起点 2：

• 2 → 3：和 5，不满足
• 2 → -3：和 -1，不满足

起点 -2、3、-3： 没有子节点，凑不出长度 ≥ 2 的路径。

合计 2 条，与样例输出一致。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举+DFS	O(N²)	O(N)	N 为节点数，最坏情况每个节点作为起点遍历整棵树

---

易错点总结

1. 建树时的 None 处理

层序遍历建树时，None 表示空节点，不占队列位置但需要正确推进索引。

2. 路径长度判断

必须在 DFS 向下走之后才判断长度，不能仅判断长度为 2 的边。路径长度是节点数，不是边数。

3. 每个起点独立计数

同一个节点可能作为多条路径的起点，也可能出现在其他路径的中间，每次都要独立统计。

---

扩展思考

• 前缀和优化： 对于单链（每个节点只有一个子节点），可以用前缀和 + HashSet 在 O(N) 内解决。
• 路径问题变体： 若允许向上回溯，问题变为求所有和为 0 的路径，可以用前缀和 + HashMap 解决。
• 树上的路径问题： 很多树的路径问题都可以通过"固定起点 + DFS"或"前缀和 + HashMap"来解决。

---

相关题目

• 最大传播链 — 图上的最长路径