← Static tasks

536. Construct Binary Tree from String

leetcode medium

#csharp#leetcode#medium#recursion#string#tree#two-pointers

Task

Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел.

Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой.

Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует.

Пример:

Input: s = "4(2(3)(1))(6(5))"

Output: [4,2,6,3,1,5]

C# solution

matched/original
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++ solution

auto-draft, review before submit
#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 solution

matched/original
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 solution

matched/original
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 solution

matched/original
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 solution

matched/original
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
}

Explanation

Algorithm

Извлечение числа:

Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть.

Построение поддерева:

Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки.

Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют.

Основная функция:

Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево.

😎