606. Construct String from Binary Tree

leetcode medium

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

Task

Дано корневой узел бинарного дерева, ваша задача — создать строковое представление дерева, следуя определенным правилам форматирования. Представление должно быть основано на прямом обходе бинарного дерева и должно соответствовать следующим требованиям:

Представление узлов

: Каждый узел в дереве должен быть представлен его целочисленным значением.

Скобки для дочерних узлов

: Если у узла есть хотя бы один дочерний узел (левый или правый), его дочерние узлы должны быть представлены в скобках. Конкретно:

- Если у узла есть левый дочерний узел, значение левого дочернего узла должно быть заключено в скобки сразу после значения узла.

- Если у узла есть правый дочерний узел, значение правого дочернего узла также должно быть заключено в скобки. Скобки для правого дочернего узла должны следовать за скобками для левого дочернего узла.

Пропуск пустых скобок

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

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

Пример:

Input: root = [1,2,3,4]

Output: "1(2(4))(3)"

Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

C# solution

matched/original

public class Solution {
    public string Tree2str(TreeNode t) {
        var res = new StringBuilder();
        Dfs(t, res);
        return res.ToString();
    }
    private void Dfs(TreeNode t, StringBuilder res) {
        if (t == null) return;
        res.Append(t.val);
        if (t.left == null && t.right == null) return;
        res.Append('(');
        Dfs(t.left, res);
        res.Append(')');
        if (t.right != null) {
            res.Append('(');
            Dfs(t.right, res);
            res.Append(')');
        }
    }
}

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.
class Solution {
public:
    public string Tree2str(TreeNode t) {
        var res = new StringBuilder();
        Dfs(t, res);
        return res.ToString();
    }
    private void Dfs(TreeNode t, StringBuilder res) {
        if (t == null) return;
        res.Append(t.val);
        if (t.left == null && t.right == null) return;
        res.Append('(');
        Dfs(t.left, res);
        res.Append(')');
        if (t.right != null) {
            res.Append('(');
            Dfs(t.right, res);
            res.Append(')');
        }
    }
}

Java solution

matched/original

public class Solution {
    public String tree2str(TreeNode t) {
        StringBuilder res = new StringBuilder();
        dfs(t, res);
        return res.toString();
    }

    private void dfs(TreeNode t, StringBuilder res) {
        if (t == null)
            return;
        res.append(t.val);
        if (t.left == null && t.right == null)
            return;
        res.append('(');
        dfs(t.left, res);
        res.append(')');
        if (t.right != null) {
            res.append('(');
            dfs(t.right, res);
            res.append(')');
        }
    }
}

JavaScript solution

matched/original

var tree2str = function(t) {
    const dfs = (t) => {
        if (!t) return "";
        let res = `${t.val}`;
        if (!t.left && !t.right) return res;
        res += `(${dfs(t.left)})`;
        if (t.right) {
            res += `(${dfs(t.right)})`;
        }
        return res;
    }
    return dfs(t);
};

Python solution

matched/original

class Solution:
    def tree2str(self, t: TreeNode) -> str:
        def dfs(t):
            if not t:
                return ""
            res = str(t.val)
            if not t.left and not t.right:
                return res
            res += f"({dfs(t.left)})"
            if t.right:
                res += f"({dfs(t.right)})"
            return res
        return dfs(t)

Go solution

matched/original

import (
    "strconv"
)

func tree2str(t *TreeNode) string {
    var res string
    dfs(t, &res)
    return res
}

func dfs(t *TreeNode, res *string) {
    if t == nil {
        return
    }
    *res += strconv.Itoa(t.Val)
    if t.Left == nil && t.Right == nil {
        return
    }
    *res += "("
    dfs(t.Left, res)
    *res += ")"
    if t.Right != nil {
        *res += "("
        dfs(t.Right, res)
        *res += ")"
    }
}

Explanation

Algorithm

Инициализация и рекурсия

Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

Обработка дочерних узлов

Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

Объединение результатов

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

😎