刷题笔记合集🔗

问题描述

请按下列描述构建一颗二叉树,并返回该树的根节点:

1. 先创建值为-1的根结点,根节点在第0层
2. 然后根据operations依次添加节点:operations[i]=[height,index]表示对第height层的第index个节点node,添加值为i的子节点:
   • 若node无「左子节点」,则添加左子节点
   • 若node有「左子节点」,但无「右子节点」,则添加右子节点
   • 否则不作任何处理

height、index均从0开始计数;index指所在层的创建顺序。

输入格式

一个二维数组operations,每个元素为[height,index]。

输出格式

根据返回的树根节点,按照层序遍历二叉树打印的结果。

备注

• 1 <= operations.length <= 100
• operations[i].length == 2
• 0 <= operations[i][0] < 100
• 0 <= operations[i][1] < 100
• 输入用例保证每次操作对应的节点已存在

样例1

输入:

[[0, 0], [0, 0], [1, 1], [1, 0], [0, 0]]

输出:

[-1, 0, 1, 3, null, 2]

说明:首个值是根节点的值,也是返回值;null表示是空节点,此特殊层序遍历会遍历有值节点的null子节点

样例2

输入:

[[0, 0], [1, 0], [1, 0], [2, 1], [2, 1], [2, 1], [2, 0], [3, 1], [2, 0]]

输出:

[-1, 0, null, 1, 2, 6, 8, 3, 4, null, null, null, null, null, null, 7]

说明:首个值是根节点的值,也是返回值;null表示是空节点,此特殊层序遍历会遍历有值节点的null子节点

题解

本题的关键在于:

1. 使用二维数组tree记录每层节点的创建顺序:
   • tree[height][index]表示第height层第index个创建的节点
   • 只记录成功插入的节点
2. 节点插入规则:
   • 无左子节点时插入左子节点
   • 有左无右时插入右子节点
   • 否则不插入
3. 层序遍历输出时:
   • 需要输出null子节点
   • 末尾的null可以省略

参考代码

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def getResult(operations):
    # 初始化树结构
    tree = [[Node(-1)]]
    
    # 按operations添加节点
    for i, (height, index) in enumerate(operations):
        # 创建新节点
        node = Node(i)
        
        # 获取父节点
        parent = tree[height][index]
        
        # 尝试插入新节点
        if not parent.left:
            parent.left = node
            # 确保下一层列表存在
            if len(tree) <= height + 1:
                tree.append([])
            # 只记录成功插入的节点
            tree[height + 1].append(node)
        elif not parent.right:
            parent.right = node
            if len(tree) <= height + 1:
                tree.append([])
            tree[height + 1].append(node)
    
    # 层序遍历输出
    result = []
    queue = [tree[0][0]]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
            
    # 移除末尾的null
    while result and result[-1] is None:
        result.pop()
        
    return result

# 处理输入
operations = eval(input())
print(getResult(operations))

import java.util.*;

class Node {
    int val;
    Node left;
    Node right;
    
    Node(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        
        // 解析输入的二维数组
        int[][] operations = parseInput(input);
        
        // 处理结果
        List<Integer> result = getResult(operations);
        
        // 格式化输出
        System.out.println(formatOutput(result));
    }
    
    public static List<Integer> getResult(int[][] operations) {
        // 初始化树结构
        List<List<Node>> tree = new ArrayList<>();
        tree.add(new ArrayList<>());
        tree.get(0).add(new Node(-1));
        
        // 按operations添加节点
        for(int i = 0; i < operations.length; i++) {
            int height = operations[i][0];
            int index = operations[i][1];
            
            // 创建新节点
            Node node = new Node(i);
            
            // 获取父节点
            Node parent = tree.get(height).get(index);
            
            // 尝试插入新节点
            if(parent.left == null) {
                parent.left = node;
                // 确保下一层列表存在
                while(tree.size() <= height + 1) {
                    tree.add(