二叉树无相邻节点最大和求解及对应贡献节点名称列表获取

原来的maxSumHelper仅返回「选当前节点」「不选当前节点」两个状态的最大权值和，我们只需要把返回值扩展为同时携带对应状态下的节点列表即可。
每个递归返回的结果包含两个元组：

• 第一个元组：(选当前节点时的最大和, 对应的节点名称列表)
• 第二个元组：(不选当前节点时的最大和, 对应的节点名称列表)

# Python3 program to find maximum sum in Binary
# Tree such that no two nodes are adjacent.

# Binary Tree Node

""" utility that allocates a newNode
with the given key """
class newNode:

    # Construct to create a newNode
    def __init__(self, key, name):
        self.data = key
        self.name = name
        self.left = None
        self.right = None

def maxSumHelper(root) :

    if (root == None):
        # 空节点两个状态均为和0、空列表
        return (0, []), (0, [])
    
    left_inc, left_exc = maxSumHelper(root.left)
    right_inc, right_exc = maxSumHelper(root.right)

    # 情况1：选中当前节点，左右子节点均不可选
    inc_sum = left_exc[0] + right_exc[0] + root.data
    inc_list = left_exc[1] + right_exc[1] + [root.name]

    # 情况2：不选中当前节点，左右子树各自取最优状态
    if left_inc[0] > left_exc[0]:
        left_best_sum, left_best_list = left_inc
    else:
        left_best_sum, left_best_list = left_exc
    
    if right_inc[0] > right_exc[0]:
        right_best_sum, right_best_list = right_inc
    else:
        right_best_sum, right_best_list = right_exc
    
    exc_sum = left_best_sum + right_best_sum
    exc_list = left_best_list + right_best_list

    return (inc_sum, inc_list), (exc_sum, exc_list)

def maxSum(root) :
    inc_res, exc_res = maxSumHelper(root)
    # 返回和更大的结果，若和相等默认取不选根的方案，可按需调整
    if inc_res[0] > exc_res[0]:
        return inc_res
    return exc_res

# Driver Code
if __name__ == '__main__':
    root = newNode(10, 'a')
    root.left = newNode(1, 'b')
    root.left.left = newNode(2, 'c')
    root.left.left.left = newNode(1, 'd')
    root.left.right = newNode(3, 'e')
    root.left.right.left = newNode(4, 'f')
    root.left.right.right = newNode(5, 'g')
    max_val, node_list = maxSum(root)
    print("最大权值和：", max_val)
    print("贡献最大和的节点列表：", node_list)

最大权值和： 21
贡献最大和的节点列表： ['c', 'f', 'g', 'a']

如果需要按树的遍历顺序调整列表顺序，或者需要收集所有等值最优解，可以基于上述逻辑进一步扩展。

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