java - DFS - Java递归 - 找到节点的总和

Question

下面是我的代码：

class Node{
    int value;
    Node left;
    Node right;
    Node parent;
       //getters, setters
}

创建树

    private static void createTree() throws FileNotFoundException{
    Map<String,Node> nodeMap = new HashMap<String,Node>();
    Scanner sc = new Scanner(new File("<location>"));
    int row =0;
    while(sc.hasNextLine()){
        String line = sc.nextLine();
        Scanner scanLine = new Scanner(line);
        System.out.println(line);
        int col =0;

        while(scanLine.hasNextInt()){
            int value = scanLine.nextInt();
            System.out.println(row+","+col+"="+value);
            Node node = new Node(value);
            nodeMap.put(row+","+col,node);
            if(row >0){
                if(col %2 ==0){
                    //left node
                    Node parent = nodeMap.get(row-1+","+col/2);
                    if(parent !=null){
                        node.setParent(parent);
                        parent.setLeft(node);
                    }
                }else{
                    //right node
                    Node parent = nodeMap.get(row-1+","+(col-1)/2);
                    if(parent !=null){
                        node.setParent(parent);
                        parent.setRight(node);
                    }
                }
            }
            col++;
        }
        row++;
    }
    System.out.println(nodeMap);
    Node root = nodeMap.get("0,0");
    traverseTree(root);
    System.out.println("sum="+sum);


}

实际遍历

    static int sum =0;
private static void traverseTree(Node n){
    if(n != null){
        sum+=n.value;
        traverseTree(n.left);
        traverseTree(n.right);
    }
}

我有两个问题：

1. 读取输入并创建树：我从文件中读取它并将根节点存储在哈希图中。有哪些替代方案？

2. 在递归搜索中，我将总和保留在函数之外，因此可以按顺序计算总和。是否可以将 sum 变量保留在内部并在最后返回总值？

Answer 1

我从文件中读取它并将根节点存储在哈希图中。有哪些替代方案？

考虑到明显的输入格式，您的操作方式似乎很合理，但是我建议使用 aList<List<Node>>而不是将其与字符串一起存储，因为您的性能可能会很快下降，因为字符串非常相似，这可能会导致哈希冲突，从而降低您的性能如果输入很大，map 的性能会大大提高。

在递归搜索中，我将总和保留在函数之外，因此可以按顺序计算总和。是否可以将 sum 变量保留在内部并在最后返回总值？

private static int traverseTree(Node n) {
    if (n != null) {
        return n.value + traverseTree(n.left) + traverseTree(n.right);
    } else {
        return 0;
    }
}