左孩子右兄弟（LC-RS）树无相邻节点的最大节点和算法如何实现？

前置说明 #

LC-RS（左孩子右兄弟）树的每个节点包含两个指针：左指针指向自身的第一个子节点，右指针指向同层级的下一个兄弟节点。本算法基于树形动态规划实现，适配LC-RS树的结构特性，时间复杂度为O(n)（n为节点总数，每个节点仅遍历一次），空间复杂度为O(h)（h为树高，为递归栈深度）。

核心状态定义 #

我们通过两个递归函数分别处理单节点子树、同层级兄弟序列，每个函数返回两个状态值：

1. dfs_node(node)：处理单个节点及其所有后代（不包含兄弟节点），返回值为(select, not_select)
   • select：选中当前节点时，该节点子树的最大和
   • not_select：不选中当前节点时，该节点子树的最大和
2. dfs_sibling(node)：处理以node为起点的所有同层级兄弟节点（含各自子树），返回值为(allow, forbid)
   • allow：兄弟序列可自由选择节点（符合无相邻规则）时的最大和
   • forbid：兄弟序列所有节点都禁止选中时的最大和（用于父节点被选中的场景）

递推规则 #

边界条件 #

若输入节点为空，两个函数均返回(0, 0)

dfs_sibling递推逻辑 #

假设当前处理节点为cur，其右兄弟序列的返回值为(sib_allow, sib_forbid)，当前节点自身的子树返回值为(cur_sel, cur_not)：

• 所有节点禁止选中的场景：当前节点不能选（取cur_not） + 后续兄弟也都禁止选中（取sib_forbid），即forbid = cur_not + sib_forbid
• 可自由选择的场景：取两种情况的最大值
  • 选中当前节点：当前节点子树取cur_sel + 后续兄弟可自由选择（兄弟与当前节点无相邻关系）取sib_allow
  • 不选中当前节点：当前节点子树取cur_not + 后续兄弟可自由选择取sib_allow
    即allow = max(cur_sel + sib_allow, cur_not + sib_allow)

dfs_node递推逻辑 #

假设当前处理节点为cur，其所有子节点组成的兄弟序列的返回值为(child_allow, child_forbid)：

• 选中当前节点：所有直接子节点都不能选，取cur.val + child_forbid
• 不选中当前节点：子节点可自由选择，取child_allow

代码示例（C++） #

struct LCRSNode {
    int val;
    LCRSNode* left_child;
    LCRSNode* right_sibling;
};

// 返回(allow_sel, forbid_sel)
pair<int, int> dfs_sibling(LCRSNode* node) {
    if (!node) return {0, 0};
    // 先处理右侧兄弟序列
    auto [sib_allow, sib_forbid] = dfs_sibling(node->right_sibling);
    // 处理当前节点的子树
    auto [cur_sel, cur_not] = dfs_node(node);
    // 计算当前序列的两个状态
    int forbid = cur_not + sib_forbid;
    int allow = max(cur_sel + sib_allow, cur_not + sib_allow);
    return {allow, forbid};
}

// 返回(select_cur, not_select_cur)
pair<int, int> dfs_node(LCRSNode* node) {
    if (!node) return {0, 0};
    // 处理当前节点的所有子节点组成的兄弟序列
    auto [child_allow, child_forbid] = dfs_sibling(node->left_child);
    int select = node->val + child_forbid;
    int not_select = child_allow;
    return {select, not_select};
}

int maxSum(LCRSNode* root) {
    auto [sel, not_sel] = dfs_node(root);
    return max(sel, not_sel);
}

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