" class="reference-link">1. 题目描述

2. 题目分析

题目意思很简单，遍历树的每一条路径，然后相加，返回最后结果
思路一：DFS【每次看代码就秒懂，自己每次都想不到】：递递归归，莫有脑袋。每次递归加上从一开始的值
思路二：BFS【个人最喜欢的】：维护两个队列，队列一存放root，队列二存放val，每次遍历抛出，队列二种始终更新这一条分树的值，最后相加

3. 题目代码

3.1 DFS

public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    public static int dfs(TreeNode root, int prevSum) {
        if (root == null) {
            return 0;
        }
        // 最开始是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);
        }
    }

3.2 BFS

public int sumNumbers1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> queue1 = new LinkedList<Integer>();
        int sum = 0;
        queue.add(root);
        queue1.add(root.val);
        while (!queue.isEmpty()) {
            TreeNode tempNode = queue.poll();
            int num = queue1.poll();
            if(tempNode.left == null && tempNode.right == null) {
                System.out.println(num);
                sum += num;
            }else {
                if(tempNode.left != null) {
                    queue.add(tempNode.left);
                    queue1.add(num * 10 + tempNode.val);
                }
                if(tempNode.right != null) {
                    queue.add(tempNode.right);
                    queue1.add(num * 10 + tempNode.val);
                }
            }
        }
        return sum;
    }