刷題筆記合集??

問題描述

請按下列描述構建一顆二叉樹,并返回該樹的根節(jié)點:

1. 先創(chuàng)建值為-1的根結點,根節(jié)點在第0層
2. 然后根據(jù)operations依次添加節(jié)點:operations[i]=[height,index]表示對第height層的第index個節(jié)點node,添加值為i的子節(jié)點:
   • 若node無「左子節(jié)點」,則添加左子節(jié)點
   • 若node有「左子節(jié)點」,但無「右子節(jié)點」,則添加右子節(jié)點
   • 否則不作任何處理

height、index均從0開始計數(shù);index指所在層的創(chuàng)建順序。

輸入格式

一個二維數(shù)組operations,每個元素為[height,index]。

輸出格式

根據(jù)返回的樹根節(jié)點,按照層序遍歷二叉樹打印的結果。

備注

• 1 <= operations.length <= 100
• operations[i].length == 2
• 0 <= operations[i][0] < 100
• 0 <= operations[i][1] < 100
• 輸入用例保證每次操作對應的節(jié)點已存在

樣例1

輸入:

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

輸出:

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

說明:首個值是根節(jié)點的值,也是返回值;null表示是空節(jié)點,此特殊層序遍歷會遍歷有值節(jié)點的null子節(jié)點

樣例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]

說明:首個值是根節(jié)點的值,也是返回值;null表示是空節(jié)點,此特殊層序遍歷會遍歷有值節(jié)點的null子節(jié)點

題解

本題的關鍵在于:

1. 使用二維數(shù)組tree記錄每層節(jié)點的創(chuàng)建順序:
   • tree[height][index]表示第height層第index個創(chuàng)建的節(jié)點
   • 只記錄成功插入的節(jié)點
2. 節(jié)點插入規(guī)則:
   • 無左子節(jié)點時插入左子節(jié)點
   • 有左無右時插入右子節(jié)點
   • 否則不插入
3. 層序遍歷輸出時:
   • 需要輸出null子節(jié)點
   • 末尾的null可以省略

參考代碼

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

def getResult(operations):
    # 初始化樹結構
    tree = [[Node(-1)]]
    
    # 按operations添加節(jié)點
    for i, (height, index) in enumerate(operations):
        # 創(chuàng)建新節(jié)點
        node = Node(i)
        
        # 獲取父節(jié)點
        parent = tree[height][index]
        
        # 嘗試插入新節(jié)點
        if not parent.left:
            parent.left = node
            # 確保下一層列表存在
            if len(tree) <= height + 1:
                tree.append([])
            # 只記錄成功插入的節(jié)點
            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();
        
        // 解析輸入的二維數(shù)組
        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添加節(jié)點
        for(int i = 0; i < operations.length; i++) {
            int height = operations[i][0];
            int index = operations[i][1];
            
            // 創(chuàng)建新節(jié)點
            Node node = new Node(i);
            
            // 獲取父節(jié)點
            Node parent = tree.get(height).get(index);
            
            // 嘗試插入新節(jié)點
            if(parent.left == null) {
                parent.left = node;
                // 確保下一層列表存在
                while(tree.size() <= height + 1) {
                    tree.add(