计算从根到叶子节点生成的所有数字之和

基本思路，是深度优先遍历和回溯算法，逻辑是先序遍历

import java.util.ArrayList;
import java.util.Scanner;

class Node{
    public int val;
    public Node left = null;
    public Node right = null;

    public Node(int val){
        this.val = val;
    }
}
public class Main {
    private static ArrayList<Integer> array;
    private static int sumNum;
    public static void main(String[] args) {
        // 建立一颗二叉树
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> arr = new ArrayList<>();
        while(sc.hasNext()){
            arr.add(sc.nextInt());
        }
        Node root = buildTree(arr);
        sc.close();

        // 初始化
        sumNum = 0;
        array = new ArrayList<>();
        dfs(root);
        System.out.println(sumNum);
    }

    public static Node buildTree(ArrayList<Integer> arr){
        if(arr.size() == 0) return null;
        int message = arr.remove(0);
        if(message == -1){
            return null;
        }
        Node node = new Node(message);
        node.left = buildTree(arr);
        node.right = buildTree(arr);
        return node;
    }

    public static void dfs(Node node){
        if(node == null){
            return;
        }
        if(node.left == null && node.right == null){
            //计算出路径的值
            int cal = 0;
            for(Integer integer:array){
                cal = cal*10 + integer;
            }
            cal =  cal*10 + node.val;
            // 累加
            sumNum += cal;
        }else{
            array.add(node.val);
            dfs(node.left);
            dfs(node.right);
            array.remove(array.size()-1);
        }
    }
}