深度广度优先搜索TreeNode

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

public class TreeNode{
	int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){}
    TreeNode(int val){this.val = val}
    TreeNode(int val,TreeNode left,TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right; 
    }
}

public TreeNode createBT(int[] arr,int i){
    if(i>arr.length){
        return null;
    }
    if(arr[i-1] == null){
        return null;
    }
    TreeNode root = new TreeNode(arr[i-1]);
    root.left = createBT(arr,2*i);
    root.right = createBT(arr,2*i+1);
}

class Solution{
    public int sumNumbers(TreeNode root){
        return dfs(root,0);
    }
    
    public int dfs(TreeNode root, int prevSum){
        if(root == null){
            return 0;
        }
        
        int sum = prevSum * 10 + root.val;
        if(root.left == null && root.right == null){
            return sum;
        }else{
            return dfs(root.left,sum)+dfs(root.right,sum);
        }
    }
}

class Solution{
    public int sumNumbers(TreeNode root){
        if(root == null){
            return 0;
        }
        int sum = 0;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> numQueue = new LinkedList<Integer>();
        nodeQueue.offer(root);
        numQueue.offer(root.val);
        while(!nodeQueue.isEmpty()){
            TreeNode node = nodeQueue.poll();
            int num = numQueue.poll();
            TreeNode left = node.left,right = node.right;
            if(left == null && right == null){ 
                sum += num;
            }else{
                if(left != null){
                    nodeQueue.offer(left);
                    numQueue.offer(num * 10 + left.val);
                }
                if(right != null){
                    nodeQueue.offer(right);
                    numQueue.offer(num * +right.val);
                }
            }
        }
        return sum;
    }
}