【力扣每日一题】129. 求根到叶子节点数字之和-阿里云开发者社区

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

2023-12-29 33

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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