华为OD机试 Python 【创建二叉树】

Dear 丶 2024-03-08 06:24 90阅读 0赞

### 题目 ###

请按照以下步骤，构建一个二叉树，并返回它的根节点。

开始时，建立一个值为-1的根节点。这是第0层。  
根据操作列表operations，逐一添加节点。列表中的每个操作\[height, index\]表示：  
height：节点所在层  
index：节点在该层的位置（从0开始）  
添加规则如下：

如果目标节点没有左子节点，添加一个新的子节点到左边。  
如果目标节点有左子节点但没有右子节点，添加一个新的子节点到右边。  
如果目标节点已经有左右子节点，就不添加。  
注意点：

输入保证操作中的节点始终存在。  
最后的输出是一个按层次遍历的节点值列表，可能包含null来表示空节点。

示例：  
输入：  
\[\[0, 0\], \[0, 0\], \[1, 1\], \[1, 0\], \[0, 0\]\]  
输出：  
\[-1, 0, 1, 3, null, 2\]

### 代码 ###

class TreeNode:
        def __init__(self, value: int):
            self.val = value
            self.left = None
            self.right = None
    
    def build_tree(ops: list[list[int]]) -> TreeNode:
        # 初始化树，根节点值为-1
        layers = [[TreeNode(-1)]]
    
        for idx, (layer, pos) in enumerate(ops):
            parent = layers[layer][pos]
    
            # 创建新节点
            new_child = TreeNode(idx)
    
            # 确定新节点是左子节点还是右子节点
            if not parent.left:
                parent.left = new_child
            elif not parent.right:
                parent.right = new_child
    
            # 如果是新的层，添加新层
            if len(layers) == layer + 1:
                layers.append([])
    
            # 更新layers的结构
            if parent.left == new_child or parent.right == new_child:
                layers[layer + 1].append(new_child)
    
        return layers[0][0]
    
    def traverse_level_order(root: TreeNode) -> list[Union[int, str]]:
        # 层序遍历
        if not root:
            return []
    
        result = []
        queue = [root]
    
        while queue:
            node = queue.pop(0)
    
            if node:
                result.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")
    
        # 清除尾部的"null"
        while result and result[-1] == "null":
            result.pop()
    
        return result
    
    if __name__ == "__main__":
        ops = eval(input())
        root = build_tree(ops)
        print(traverse_level_order(root))