655. Print Binary Tree
LeetCode
medium
original: C#
#csharp
#leetcode
#math
#matrix
#medium
#recursion
#search
#string
#tree
#two-pointers
선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.
given корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)
/2
]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". return построенную матрицу res.
예제:
Input: root = [1,2]
Output:
[["","1",""],
["2","",""]]
C# 해법
매칭됨/원본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++ 해법
자동 초안, 제출 전 검토#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 해법
매칭됨/원본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 해법
매칭됨/원본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 해법
매칭됨/원본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 resGo 해법
매칭됨/원본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 заполненную матрицу.
😎
Vacancies for this task
활성 채용 with overlapping task tags are 표시됨.
아직 활성 채용이 없습니다.