LeetCode 988：回溯和深度优先搜索（DFS）之间的差异

Question

我对LeetCode 988（从Leaf开头的最小字符串）中的回溯解决方案和DFS解决方案感到困惑。

如果使用StringBuilder实现，则需要以下代码行：sb.deleteCharAt(sb.length() - 1)，而使用String实现时，则不需要该行。

有人可以帮助解决我的困惑吗？

Backtracking（使用StringBuilder）

String ans = "";

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

private void helper(TreeNode root, StringBuilder sb) {
    if (root == null) return;
    sb.append((char)('a' + root.val));
    if (root.left == null && root.right == null) {
    String candidate = sb.reverse().toString();
    if (ans == "" || candidate.compareTo(ans) < 0) {
        ans = candidate;
        sb.reverse();
    }

    helper(root.left, sb);
    helper(root.right, sb);
    sb.deleteCharAt(sb.length() - 1);
}

DFS（使用字符串）

String ans = "";

public String smallestFromLeaf(TreeNode root) {
    helper(root, "");
    return ans;
}

private void helper(TreeNode root, String s) {
    if (root == null) return;

    s = (char)('a' + root.val) + s;
    if (root.left == null && root.right == null) {
        String candidate = s;
        if (ans == "" || candidate.compareTo(ans) < 0) {
            ans = candidate;
        }
        return;
    }

    helper(root.left, s);
    helper(root.right, s);
}

Answer 1

字符串在Java中不是可变的，这意味着该行，

s = (char)('a' + root.val) + s;

将创建一个递归函数接收的新String对象。因此，没有回溯解决方案通常具有的“撤消”步骤。而在回溯解决方案中，仅创建和传递一个StringBuilder对象。当我们从回溯解决方案中的基本情况返回时（即到达叶节点），我们必须取消将字符添加到字符串生成器的步骤。

我建议您将打印语句添加到回溯解决方案的sb状态以及DFS中s的值，并查看其如何改变递归的每个步骤。