655. Print Binary Tree

LeetCode medium original: C# #csharp #leetcode #math #matrix #medium #recursion #search #string #tree #two-pointers

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

given корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)

]).

Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". return построенную матрицу res.

Beispiel:

Input: root = [1,2]

Output:

[["","1",""],

["2","",""]]

C# Lösung

zugeordnet/original

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    private int FindHeight(TreeNode root) {
        if (root == null) return -1;
        return 1 + Math.Max(FindHeight(root.left), FindHeight(root.right));
    }
    private void Fill(string[,] res, TreeNode root, int r, int c, int height) {
        if (root == null) return;
        res[r, c] = root.val.ToString();
        if (root.left != null) {
            Fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height);
        }
        if (root.right != null) {
            Fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height);
        }
    }
    public IList<IList<string>> PrintTree(TreeNode root) {
        int height = FindHeight(root);
        int m = height + 1;
        int n = (1 << (height + 1)) - 1;
        string[,] res = new string[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[i, j] = "";
            }
        }
        Fill(res, root, 0, (n - 1) / 2, height);
        IList<IList<string>> result = new List<IList<string>>();
        for (int i = 0; i < m; i++) {
            IList<string> row = new List<string>();
            for (int j = 0; j < n; j++) {
                row.Add(res[i, j]);
            }
            result.Add(row);
        }
        return result;
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    private int FindHeight(TreeNode root) {
        if (root == null) return -1;
        return 1 + max(FindHeight(root.left), FindHeight(root.right));
    }
    private void Fill(string[,] res, TreeNode root, int r, int c, int height) {
        if (root == null) return;
        res[r, c] = root.val.ToString();
        if (root.left != null) {
            Fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height);
        }
        if (root.right != null) {
            Fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height);
        }
    }
    public IList<vector<string>> PrintTree(TreeNode root) {
        int height = FindHeight(root);
        int m = height + 1;
        int n = (1 << (height + 1)) - 1;
        string[,] res = new string[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[i, j] = "";
            }
        }
        Fill(res, root, 0, (n - 1) / 2, height);
        IList<vector<string>> result = new List<vector<string>>();
        for (int i = 0; i < m; i++) {
            vector<string> row = new List<string>();
            for (int j = 0; j < n; j++) {
                row.push_back(res[i, j]);
            }
            result.push_back(row);
        }
        return result;
    }
}

Java Lösung

zugeordnet/original

import java.util.ArrayList;
import java.util.List;

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

public class Solution {
    private int findHeight(TreeNode root) {
        if (root == null) return -1;
        return 1 + Math.max(findHeight(root.left), findHeight(root.right));
    }

    private void fill(String[][] res, TreeNode root, int r, int c, int height) {
        if (root == null) return;
        res[r][c] = Integer.toString(root.val);
        if (root.left != null) {
            fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height);
        }
        if (root.right != null) {
            fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height);
        }
    }

    public List<List<String>> printTree(TreeNode root) {
        int height = findHeight(root);
        int m = height + 1;
        int n = (1 << (height + 1)) - 1;
        String[][] res = new String[m][n];
        for (String[] row : res) {
            Arrays.fill(row, "");
        }
        fill(res, root, 0, (n - 1) / 2, height);
        List<List<String>> result = new ArrayList<>();
        for (String[] row : res) {
            result.add(Arrays.asList(row));
        }
        return result;
    }
}

JavaScript Lösung

zugeordnet/original

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

const findHeight = (root) => {
    if (!root) return -1;
    return 1 + Math.max(findHeight(root.left), findHeight(root.right));
}

const fill = (res, root, r, c, height) => {
    if (!root) return;
    res[r][c] = root.val.toString();
    if (root.left) {
        fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height);
    }
    if (root.right) {
        fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height);
    }
}

const printTree = (root) => {
    const height = findHeight(root);
    const m = height + 1;
    const n = (1 << (height + 1)) - 1;
    const res = Array.from({ length: m }, () => Array(n).fill(""));
    fill(res, root, 0, Math.floor((n - 1) / 2), height);
    return res;
}

Python Lösung

zugeordnet/original

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

def findHeight(root):
    if not root:
        return -1
    return 1 + max(findHeight(root.left), findHeight(root.right))

def fill(res, root, r, c, height):
    if not root:
        return
    res[r][c] = str(root.val)
    if root.left:
        fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height)
    if root.right:
        fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height)

def printTree(root):
    height = findHeight(root)
    m = height + 1
    n = (1 << (height + 1)) - 1
    res = [["" for _ in range(n)] for _ in range(m)]
    fill(res, root, 0, (n - 1) // 2, height)
    return res

Go Lösung

zugeordnet/original

package main

import (
    "fmt"
    "strconv"
    "strings"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func findHeight(root *TreeNode) int {
    if root == nil {
        return -1
    }
    leftHeight := findHeight(root.Left)
    rightHeight := findHeight(root.Right)
    if leftHeight > rightHeight {
        return 1 + leftHeight
    }
    return 1 + rightHeight
}

func fill(res [][]string, root *TreeNode, r, c, height int) {
    if root == nil {
        return
    }
    res[r][c] = strconv.Itoa(root.Val)
    if root.Left != nil {
        fill(res, root.Left, r+1, c-(1<<(height-r-1)), height)
    }
    if root.Right != nil {
        fill(res, root.Right, r+1, c+(1<<(height-r-1)), height)
    }
}

func printTree(root *TreeNode) [][]string {
    height := findHeight(root)
    m := height + 1
    n := (1 << (height + 1)) - 1
    res := make([][]string, m)
    for i := range res {
        res[i] = make([]string, n)
        for j := range res[i] {
            res[i][j] = ""
        }
    }
    fill(res, root, 0, (n-1)/2, height)
    return res
}

func main() {
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}}
    result := printTree(root)
    for _, row := range result {
        fmt.Println(strings.Join(row, " "))
    }
}

Algorithm

find высоту дерева и определите размер матрицы (m x n).

Рекурсивно разместите узлы в матрице, начиная с корневого узла.

return заполненную матрицу.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.