LeetCode——1302.层数最深叶子节点的和

给你一棵二叉树的根节点 root &＃xff0c;请你返回层数最深的叶子节点的和 。

示例 1&＃xff1a;

输入&＃xff1a;root &＃61; [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出&＃xff1a;15
示例 2&＃xff1a;

输入&＃xff1a;root &＃61; [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出&＃xff1a;19

提示&＃xff1a;

• 树中节点数目在范围 [1, 104] 之间。
• 1 <&＃61; Node.val <&＃61; 100

dfs代码如下&＃xff1a;

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val &＃61; val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val &＃61; val;* this.left &＃61; left;* this.right &＃61; right;* }* }*/
class Solution {public int sum &＃61; 0;public int deepestLeavesSum(TreeNode root) {int maxDepth &＃61; depth(root);dfs(root, 1, maxDepth);return sum;}public void dfs(TreeNode root, int depth, int maxDepth) {if (root &＃61;&＃61; null) {return;}if (depth &＃61;&＃61; maxDepth) {sum &＃43;&＃61; root.val;}dfs(root.left, depth &＃43; 1, maxDepth);dfs(root.right, depth &＃43; 1, maxDepth);}public int depth(TreeNode root) {if (root &＃61;&＃61; null) {return 0;}return Math.max(depth(root.left), depth(root.right)) &＃43; 1;}
}


bfs代码如下&＃xff1a;

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val &＃61; val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val &＃61; val;* this.left &＃61; left;* this.right &＃61; right;* }* }*/
class Solution {public int deepestLeavesSum(TreeNode root) {if (root &＃61;&＃61; null) {return 0;}Queue<TreeNode> que &＃61; new LinkedList<>();que.offer(root);int ans &＃61; 0;while (!que.isEmpty()) {List<Integer> r &＃61; new ArrayList<>();int size &＃61; que.size();ans &＃61; 0;for (int i &＃61; 0; i < size; i&＃43;&＃43;) {TreeNode t &＃61; que.poll();ans &＃43;&＃61; t.val;if (t.left !&＃61; null) {que.offer(t.left);}if (t.right !&＃61; null) {que.offer(t.right);}}}return ans;}
}


执行结果&＃xff1a;