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; }
4. 总结
- 对于DFS而言，递归一定要看好入口和出口，准备开始刷刷递归的题目找找感觉。
- 对于BFS而言，队列进进出出，数值都比较明显，也便于自己操作
- 总而言之：题目刷多了，这种题就见怪不怪了。
