题目描述
给你一棵二叉树的根节点 root ,请你返回 层数最深的叶子节点的和。
解题思路
使用深度优先搜索:
- 全局维护两个变量sum(总和)以及maxdeep(最大深度)
- 对于遍历到的节点有三种情况:
(1) 此节点深度不够,不进行操作,遍历它的子节点
(2) 此节点深度与最大深度相等,sum加上这个点的值
(3) 此节点的深度更深,更新最大深度,sum取这个点的值
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//全局变量
int sum=0;
int maxdeep=1;
public int deepestLeavesSum(TreeNode root){
deepdfs(root,1);
return sum;
}
public void deepdfs(TreeNode root,int tar){
if(root==null){
return ;
}
if(tar==maxdeep){
sum+=root.val;
}else if(tar>maxdeep){
maxdeep=tar;
sum=root.val;
}
deepdfs(root.right,tar+1);
deepdfs(root.left,tar+1);
}
}
结果