带根与直接叶子二选一约束的二叉树最大分值求解算法咨询

该场景适用**树形动态规划（树形DP）**算法求解，核心逻辑是通过后序遍历二叉树，为每个节点维护两个状态，自底向上计算最优解。

状态定义 #

对每个节点，我们维护两个计算结果：

• 选当前节点：将当前节点作为所属子树的取值时，该子树能贡献的最大分值
• 不选当前节点：不选取当前节点（即取该节点所有直接子树的最优解之和）时，该子树能贡献的最大分值

状态转移规则 #

1. 若当前节点为叶子节点（无任何子节点）：
   • 选当前节点的分值就是节点自身的分值
   • 不选当前节点的分值为0（无下属子节点可以取，该子树无贡献）
2. 若当前节点为非叶子节点：
   • 选当前节点：直接取节点自身分值即可，根据约束不能再计入任何子节点的分值
   • 不选当前节点：每个直接子节点都可以自由选择自身的最优方案（选自己或选它的子节点），因此取所有子节点两个状态的最大值之和

示例验证 #

以题目给出的例子验证：子树根节点分值为2，两个直接子节点为叶子节点，分值分别为4、5：

• 两个叶子节点的最优值分别为max(4,0)=4、max(5,0)=5
• 根节点选自身的分值为2，不选自身的分值为4+5=9
• 该子树最大分值为max(2,9)=9，和规则要求一致

实现伪代码 #

# 输入：二叉树根节点root，每个节点包含val、left、right三个属性
# 返回值为元组：(选当前节点的最大分值, 不选当前节点的最大分值)
def dfs(node):
    if not node:
        return (0, 0)
    left_sel, left_not_sel = dfs(node.left)
    right_sel, right_not_sel = dfs(node.right)
    # 选当前节点
    cur_sel = node.val
    # 不选当前节点，取左右子树的最优解之和
    cur_not_sel = max(left_sel, left_not_sel) + max(right_sel, right_not_sel)
    return (cur_sel, cur_not_sel)

# 最终最大分值为根节点两个状态的最大值
root_sel, root_not_sel = dfs(root)
max_score = max(root_sel, root_not_sel)

复杂度说明 #

• 时间复杂度：O(n)，n为二叉树节点总数，每个节点仅遍历一次
• 空间复杂度：O(h)，h为二叉树高度，为递归栈的开销

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