Java

Question

如果 b 是 a 的子节点，问题是要求输出字符串数组列表中二叉树中所有路径的输出，格式为 a->b。 =16=]

我收到以下错误消息，但我认为“路径”、“dfs”拼写和使用正确：

/code/Solution.java:41: error: cannot find symbol
paths.add(updated);
^
symbol: variable updated
location: class Solution
/code/Solution.java:46: error: cannot find symbol
dfs(paths, updated, toSearch.left);
^
symbol: variable updated
location: class Solution
/code/Solution.java:50: error: cannot find symbol
dfs(paths, updated, toSearch.right);
^
symbol: variable updated
location: class Solution
3 errors

这是我的代码；我已经评论了我的代码以提高可读性：

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of the binary tree
     * @return: all root-to-leaf paths
     */
    public List<String> binaryTreePaths(TreeNode root) {
        // paths would be the arraylist holding all paths for returning
        List<String> paths = new ArrayList<String>();
        
        // dummy string to get the code started
        String dummy = "";

        // the first call to dfs
        dfs(paths, dummy, root);
        return paths;
    }

    /** This function adds to the arraylist "path" if the TreeNode toSearch is a leaf.
    *   Otherwise it recursively calls itself on the child nodes until reaching a leaf
    **/
    private void dfs(List<String> paths, String current, TreeNode toSearch){
        // base case
        if(toSearch == null){
            return;
        }
        // this is to take care of the initial call when the String is empty - we do not want the string to start with "->".
        if(current == ""){
            String updated = Integer.toString(toSearch.val);
        }else{
            String updated = current + "->" + toSearch.val;
        }
        
        // if both children are null, then we can append the path to the list
        if(toSearch.left == null && toSearch.right == null){
            paths.add(updated);
            return;
        }
        // if either node is not null, we keep searching.
        if(toSearch.left != null){
            dfs(paths, updated, toSearch.left);
        }

        if(toSearch.right != null){
            dfs(paths, updated, toSearch.right);
        }




    }


}

Answer 1

变量作用域在 Java 中的工作方式是，如果您在 if 语句中定义变量，它将仅在 if 语句中可用或在作用域内。此外，if 语句和 else 语句具有不同的作用域。因此，在每个范围中，都存在一个名为 updated 的变量，它是一个字符串。为了获得您想要的行为，您应该在 if 语句之外定义变量，然后使用它。

String updated = current;
if (updated.equals("")) {
    updated += toSearch.val;
} else {
    updated += "->" + toSearch.val;
}

此外，在比较字符串是否相等时，您应该使用 .equals() 而不是 ==。

Answer 2

试试这个。

record TreeNode(int val, TreeNode left, TreeNode right) {}

public static List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<>();
    dfs(paths, "", root);
    return paths;
}

static void dfs(List<String> paths, String current, TreeNode toSearch) {
    if (toSearch == null)
        return;
    current += toSearch.val;
    if (toSearch.left == null && toSearch.right == null) {
        paths.add(current);
        return;
    }
    current += "->";
    dfs(paths, current, toSearch.left);
    dfs(paths, current, toSearch.right);
}

和

public static void main(String[] args) {
    TreeNode root =
        new TreeNode(3,
            new TreeNode(1, null, null),
            new TreeNode(6,
                new TreeNode(5,
                    new TreeNode(4, null, null),
                    null),
                new TreeNode(7, null, null)));
    List<String> paths = binaryTreePaths(root);
    System.out.println(paths);
}

输出：

[3->1, 3->6->5->4, 3->6->7]

Java - 在递归 DFS 上找不到符号

Java - Cannot find symbol on a recursive DFS

recursion

depth-first-search