LeetCode 988. 从叶结点开始的最小字符串

Categories:

题目描述
思路分析
1. 解法一：DFS 回溯（推荐）
2. 解法二：DFS + 字符串拼接
相似题目

题目描述

✅ 988. 从叶结点开始的最小字符串

思路分析

解法一：DFS 回溯（推荐）

核心思路：

从根节点出发进行深度优先搜索，维护当前路径上的字符序列。

到达叶节点时，将路径字符串反转（因为题目要求从叶到根），与当前最小字符串比较并更新。

路径字符串的字典序比较需要使用字符串的自然排序，注意短字符串是长字符串前缀时的处理。

回溯时恢复路径状态，避免重复申请空间。

复杂度分析：

时间复杂度：O(n²)，其中 n 为节点数，每个叶节点路径最长为 O(n)，字符串比较为 O(n)

空间复杂度：O(n)，递归栈深度及路径存储

class Solution {
    private String result = "";

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

    private void dfs(TreeNode node, StringBuilder path) {
        if (node == null) {
            return;
        }

        // 将当前节点字符加入路径头部（从叶到根方向）
        path.insert(0, (char) ('a' + node.val));

        // 到达叶节点，比较并更新结果
        if (node.left == null && node.right == null) {
            String s = path.toString();
            if (result.isEmpty() || s.compareTo(result) < 0) {
                result = s;
            }
        }

        dfs(node.left, path);
        dfs(node.right, path);

        // 回溯，移除路径头部的字符
        path.deleteCharAt(0);
    }
}

func smallestFromLeaf(root *TreeNode) string {
    result := ""

    var dfs func(node *TreeNode, path []byte)
    dfs = func(node *TreeNode, path []byte) {
        if node == nil {
            return
        }

        // 将当前节点字符追加到路径（路径是从根到叶方向，最后反转）
        path = append(path, byte('a'+node.Val))

        // 到达叶节点，反转路径后与结果比较
        if node.Left == nil && node.Right == nil {
            // 反转路径得到从叶到根的字符串
            n := len(path)
            reversed := make([]byte, n)
            for i := 0; i < n; i++ {
                reversed[i] = path[n-1-i]
            }
            s := string(reversed)
            if result == "" || s < result {
                result = s
            }
            return
        }

        dfs(node.Left, path)
        dfs(node.Right, path)
    }

    dfs(root, []byte{})
    return result
}

解法二：DFS + 字符串拼接

核心思路：

递归时将当前节点的字符前置拼接到从子树返回的字符串上。

叶节点直接返回该节点对应的字符，内部节点则取左右子树返回值中字典序较小的，并在其前面加上当前字符。

注意处理只有单侧子树的情况，不能将空子树的结果参与比较。

复杂度分析：

时间复杂度：O(n²)，字符串拼接和比较均为 O(n)

空间复杂度：O(n²)，递归过程中字符串总空间

class Solution {
    public String smallestFromLeaf(TreeNode root) {
        if (root == null) {
            return "";
        }

        // 当前节点对应字符
        String cur = String.valueOf((char) ('a' + root.val));

        // 叶节点直接返回当前字符
        if (root.left == null && root.right == null) {
            return cur;
        }

        // 只有右子树
        if (root.left == null) {
            return smallestFromLeaf(root.right) + cur;
        }

        // 只有左子树
        if (root.right == null) {
            return smallestFromLeaf(root.left) + cur;
        }

        // 两侧子树都有，取字典序小的
        String left = smallestFromLeaf(root.left) + cur;
        String right = smallestFromLeaf(root.right) + cur;
        return left.compareTo(right) <= 0 ? left : right;
    }
}

func smallestFromLeaf(root *TreeNode) string {
    if root == nil {
        return ""
    }

    cur := string(rune('a' + root.Val))

    // 叶节点直接返回当前字符
    if root.Left == nil && root.Right == nil {
        return cur
    }

    // 只有右子树
    if root.Left == nil {
        return smallestFromLeaf(root.Right) + cur
    }

    // 只有左子树
    if root.Right == nil {
        return smallestFromLeaf(root.Left) + cur
    }

    // 两侧子树都有，取字典序小的
    left := smallestFromLeaf(root.Left) + cur
    right := smallestFromLeaf(root.Right) + cur
    if left <= right {
        return left
    }
    return right
}

相似题目

题目	难度	考察点
257. 二叉树的所有路径	简单	DFS、回溯
129. 求根节点到叶节点数字之和	中等	DFS、二叉树
112. 路径总和	简单	DFS、二叉树
113. 路径总和 II	中等	DFS、回溯
124. 二叉树中的最大路径和	困难	DFS、动态规划
543. 二叉树的直径	简单	DFS、二叉树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/91311352