536. Construct Binary Tree from String
Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел.
Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой.
Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует.
Пример:
Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]
C# решение
сопоставлено/оригиналpublic class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode Str2Tree(string s) {
return Str2TreeInternal(s, 0).Item1;
}
private Tuple<int, int> GetNumber(string s, int index) {
bool isNegative = false;
if (s[index] == '-') {
isNegative = true;
index++;
}
int number = 0;
while (index < s.Length && char.IsDigit(s[index])) {
number = number * 10 + (s[index] - '0');
index++;
}
return Tuple.Create(isNegative ? -number : number, index);
}
private Tuple<TreeNode, int> Str2TreeInternal(string s, int index) {
if (index == s.Length) return Tuple.Create<TreeNode, int>(null, index);
var numberData = GetNumber(s, index);
int value = numberData.Item1;
index = numberData.Item2;
TreeNode node = new TreeNode(value);
if (index < s.Length && s[index] == '(') {
var leftData = Str2TreeInternal(s, index + 1);
node.left = leftData.Item1;
index = leftData.Item2;
}
if (index < s.Length && s[index] == '(') {
var rightData = Str2TreeInternal(s, index + 1);
node.right = rightData.Item1;
index = rightData.Item2;
}
return Tuple.Create(node, index < s.Length && s[index] == ')' ? index + 1 : index);
}
}C++ решение
auto-draft, проверить перед отправкой#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 x) { val = x; }
}
class Solution {
public:
public TreeNode Str2Tree(string s) {
return Str2TreeInternal(s, 0).Item1;
}
private Tuple<int, int> GetNumber(string s, int index) {
bool isNegative = false;
if (s[index] == '-') {
isNegative = true;
index++;
}
int number = 0;
while (index < s.size() && char.IsDigit(s[index])) {
number = number * 10 + (s[index] - '0');
index++;
}
return Tuple.Create(isNegative ? -number : number, index);
}
private Tuple<TreeNode, int> Str2TreeInternal(string s, int index) {
if (index == s.size()) return Tuple.Create<TreeNode, int>(null, index);
var numberData = GetNumber(s, index);
int value = numberData.Item1;
index = numberData.Item2;
TreeNode node = new TreeNode(value);
if (index < s.size() && s[index] == '(') {
var leftData = Str2TreeInternal(s, index + 1);
node.left = leftData.Item1;
index = leftData.Item2;
}
if (index < s.size() && s[index] == '(') {
var rightData = Str2TreeInternal(s, index + 1);
node.right = rightData.Item1;
index = rightData.Item2;
}
return Tuple.Create(node, index < s.size() && s[index] == ')' ? index + 1 : index);
}
}Java решение
сопоставлено/оригиналclass Solution {
public TreeNode str2tree(String s) {
return this.str2treeInternal(s, 0).getKey();
}
public Pair<Integer, Integer> getNumber(String s, int index) {
boolean isNegative = false;
if (s.charAt(index) == '-') {
isNegative = true;
index++;
}
int number = 0;
while (index < s.length() && Character.isDigit(s.charAt(index))) {
number = number * 10 + (s.charAt(index) - '0');
index++;
}
return new Pair<Integer, Integer>(isNegative ? -number : number, index);
}
public Pair<TreeNode, Integer> str2treeInternal(String s, int index) {
if (index == s.length()) {
return new Pair<TreeNode, Integer>(null, index);
}
Pair<Integer, Integer> numberData = this.getNumber(s, index);
int value = numberData.getKey();
index = numberData.getValue();
TreeNode node = new TreeNode(value);
Pair<TreeNode, Integer> data;
if (index < s.length() && s.charAt(index) == '(') {
data = this.str2treeInternal(s, index + 1);
node.left = data.getKey();
index = data.getValue();
}
if (node.left != null && index < s.length() && s.charAt(index) == '(') {
data = this.str2treeInternal(s, index + 1);
node.right = data.getKey();
index = data.getValue();
}
return new Pair<TreeNode, Integer>(node, index < s.length() && s.charAt(index) == ')' ? index + 1 : index);
}
}JavaScript решение
сопоставлено/оригиналfunction TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var str2tree = function(s) {
function getNumber(s, index) {
let isNegative = false;
if (s[index] === '-') {
isNegative = true;
index++;
}
let number = 0;
while (index < s.length && !isNaN(parseInt(s[index]))) {
number = number * 10 + parseInt(s[index]);
index++;
}
return [isNegative ? -number : number, index];
}
function str2treeInternal(s, index) {
if (index === s.length) return [null, index];
let [value, newIndex] = getNumber(s, index);
let node = new TreeNode(value);
if (newIndex < s.length && s[newIndex] === '(') {
[node.left, newIndex] = str2treeInternal(s, newIndex + 1);
}
if (newIndex < s.length && s[newIndex] === '(') {
[node.right, newIndex] = str2treeInternal(s, newIndex + 1);
}
if (newIndex < s.length && s[newIndex] === ')') {
newIndex++;
}
return [node, newIndex];
}
return str2treeInternal(s, 0)[0];
};Python решение
сопоставлено/оригиналclass TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def str2tree(self, s: str) -> TreeNode:
def getNumber(s, index):
isNegative = False
if s[index] == '-':
isNegative = True
index += 1
number = 0
while index < len(s) and s[index].isdigit():
number = number * 10 + int(s[index])
index += 1
return (-number if isNegative else number, index)
def str2treeInternal(s, index):
if index == len(s):
return None, index
value, index = getNumber(s, index)
node = TreeNode(value)
if index < len(s) and s[index] == '(':
node.left, index = str2treeInternal(s, index + 1)
if index < len(s) and s[index] == '(':
node.right, index = str2treeInternal(s, index + 1)
return node, index + 1 if index < len(s) and s[index] == ')' else index
return str2treeInternal(s, 0)[0]Go решение
сопоставлено/оригиналtype TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func str2tree(s string) *TreeNode {
root, _ := str2treeInternal(s, 0)
return root
}
func getNumber(s string, index int) (int, int) {
isNegative := false
if s[index] == '-' {
isNegative = true
index++
}
number := 0
for index < len(s) && s[index] >= '0' && s[index] <= '9' {
number = number * 10 + int(s[index] - '0')
index++
}
if isNegative {
number = -number
}
return number, index
}
func str2treeInternal(s string, index int) (*TreeNode, int) {
if index == len(s) {
return nil, index
}
value, newIndex := getNumber(s, index)
node := &TreeNode{Val: value}
if newIndex < len(s) && s[newIndex] == '(' {
node.Left, newIndex = str2treeInternal(s, newIndex + 1)
}
if newIndex < len(s) && s[newIndex] == '(' {
node.Right, newIndex = str2treeInternal(s, newIndex + 1)
}
if newIndex < len(s) && s[newIndex] == ')' {
newIndex++
}
return node, newIndex
}Algorithm
Извлечение числа:
Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть.
Построение поддерева:
Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки.
Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют.
Основная функция:
Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.