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

喜欢ヅ旅行 2022-11-21 03:44 137阅读 0赞

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

# 1. 题目描述![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center] #

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f62e2bdbe7c14dc98bef04ff1af062a3.png