多叉无父引用二叉树中指定节点X的父节点查找方案咨询

1. 树节点结构构建 #

因为是子节点数量不限的树（非严格二叉树），节点需要包含值和子节点列表两个核心属性。用Python实现节点类如下：

class TreeNode:
    def __init__(self, val):
        self.val = val  # 节点唯一值
        self.children = []  # 存储所有子节点，数量无限制

手动构建树示例 #

通过创建节点对象并关联子节点，就能快速搭建树结构：

# 创建节点
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)

# 关联父子关系
root.children.extend([node2, node3])
node2.children.append(node4)
node3.children.append(node5)

最终树结构：

1
├─ 2
│  └─ 4
└─ 3
   └─5

2. 递归查找目标节点的父节点值 #

递归思路采用深度优先遍历：从根节点出发，先检查当前节点的直接子节点是否为目标；若不是，则递归遍历每个子节点的子树，一旦找到目标，就向上传递父节点值。

实现代码：

def find_parent(node, target_val):
    # 遍历当前节点的所有直接子节点
    for child in node.children:
        if child.val == target_val:
            return node.val  # 找到目标，返回当前节点值（父节点值）
        # 递归查找子节点的子树
        result = find_parent(child, target_val)
        if result is not None:
            return result  # 子树中找到目标，传递结果
    # 遍历完所有子节点仍未找到，返回None（目标是根节点或不存在）
    return None

测试示例 #

print(find_parent(root, 4))  # 输出：2
print(find_parent(root, 5))  # 输出：3
print(find_parent(root, 1))  # 输出：None（根节点无父节点）
print(find_parent(root, 6))  # 输出：None（目标节点不存在）

关键说明 #

• 利用节点值唯一的特性，无需处理重复值冲突
• 递归终止条件：找到目标节点的直接父节点，或遍历完所有节点未找到目标
• 若返回None，说明目标是根节点，或目标值不存在于树中

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