面试题：C语言指针在复杂数据结构中的深度应用

Question

假设有一个链表结构，每个节点除了包含指向下一个节点的指针外，还包含一个指针数组，该数组中的每个指针指向另一个链表的头节点（形成一种树状链表结构）。请定义这种数据结构，并编写一个递归函数，计算该结构中所有节点数据值的总和。假设节点数据值为整数类型。

Answer 1

class TreeNode:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children if children is not None else []

def sum_tree_nodes(root):
    if not root:
        return 0
    total = root.val
    for child in root.children:
        total += sum_tree_nodes(child)
    return total

可以通过以下方式调用这个函数：

# 示例创建树状链表结构
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)

node1.children = [node2, node3]
node2.children = [node4, node5]
node3.children = [node6]

print(sum_tree_nodes(node1))  

解释

1. 定义数据结构：TreeNode 类用于表示树状链表结构中的节点。每个节点包含一个数据值 val 和一个指针数组 children，指针数组中的每个指针指向另一个链表的头节点（即子节点）。

2. 递归函数 sum_tree_nodes：

   • 检查根节点是否为空，如果为空则返回0。
   • 初始化总和 total 为根节点的值。
   • 遍历根节点的所有子节点，递归调用 sum_tree_nodes 并将返回值加到 total 中。
   • 最后返回 total。

3. 示例调用：创建了一个简单的树状链表结构并调用 sum_tree_nodes 函数来计算所有节点数据值的总和。