988. Smallest String Starting From Leaf

leetcode medium

#array#backtracking#csharp#graph#leetcode#medium#prefix-sum#recursion#string#tree#two-pointers

Task

Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.

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

Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.

Например, "ab" лексикографически меньше, чем "aba".

Лист узла - это узел, у которого нет потомков.

Пример

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

Output: "dba"

C# solution

matched/original

public class Solution {
    private string ans = "~";
    public string SmallestFromLeaf(TreeNode root) {
        Dfs(root, new StringBuilder());
        return ans;
    }
    private void Dfs(TreeNode node, StringBuilder path) {
        if (node == null) return;
        path.Append((char) (node.val + 'a'));
        if (node.left == null && node.right == null) {
            var s = new string(path.ToString().Reverse().ToArray());
            if (string.Compare(s, ans) < 0) {
                ans = s;
            }
        }
        Dfs(node.left, path);
        Dfs(node.right, path);
        path.Remove(path.Length - 1, 1);
    }
}

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:
    private string ans = "~";
    public string SmallestFromLeaf(TreeNode root) {
        Dfs(root, new StringBuilder());
        return ans;
    }
    private void Dfs(TreeNode node, StringBuilder path) {
        if (node == null) return;
        path.Append((char) (node.val + 'a'));
        if (node.left == null && node.right == null) {
            var s = new string(path.ToString().Reverse().ToArray());
            if (string.Compare(s, ans) < 0) {
                ans = s;
            }
        }
        Dfs(node.left, path);
        Dfs(node.right, path);
        path.Remove(path.size() - 1, 1);
    }
}

Java solution

matched/original

public class Solution {
    private String ans = "~";

    public String smallestFromLeaf(TreeNode root) {
        dfs(root, new StringBuilder());
        return ans;
    }

    private void dfs(TreeNode node, StringBuilder path) {
        if (node == null) return;
        path.append((char) (node.val + 'a'));
        if (node.left == null && node.right == null) {
            path.reverse();
            String s = path.toString();
            path.reverse();
            if (s.compareTo(ans) < 0) {
                ans = s;
            }
        }
        dfs(node.left, path);
        dfs(node.right, path);
        path.deleteCharAt(path.length() - 1);
    }
}

JavaScript solution

matched/original

var smallestFromLeaf = function(root) {
    let ans = "~";
    
    const dfs = (node, path) => {
        if (!node) return;
        path = String.fromCharCode(node.val + 'a'.charCodeAt(0)) + path;
        if (!node.left && !node.right) {
            if (path < ans) {
                ans = path;
            }
        }
        dfs(node.left, path);
        dfs(node.right, path);
    };
    
    dfs(root, "");
    return ans;
};

Python solution

matched/original

class Solution:
    def smallestFromLeaf(self, root):
        def dfs(node, path):
            if not node:
                return
            path.append(chr(node.val + ord('a')))
            if not node.left and not node.right:
                s = "".join(reversed(path))
                if s < self.ans:
                    self.ans = s
            dfs(node.left, path)
            dfs(node.right, path)
            path.pop()
        
        self.ans = "~"
        dfs(root, [])
        return self.ans

Explanation

Algorithm

Инициализация и подготовка:

Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк).

Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы.

Обход дерева:

Если текущий узел пуст (null), просто вернитесь из функции.

Добавьте текущий символ (соответствующий значению узла) в начало строки пути.

Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше.

Рекурсивно вызовите dfs для левого и правого потомков текущего узла.

Возврат результата:

Вызовите функцию dfs с корневым узлом и пустым путем.

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

😎