【力扣每日一题】129. 求根到叶子节点数字之和

不得不说，憨憨脑袋没有递归~~~

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而言，队列进进出出，数值都比较明显，也便于自己操作
• 总而言之：题目刷多了，这种题就见怪不怪了。