Advertisement
gelita

Sum of deepest leaves

Mar 18th, 2020
752
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.27 KB | None | 0 0
  1. /**
  2. Given a binary tree, return the sum of values of its deepest leaves
  3.  * Definition for a binary tree node.
  4.  
  5.  * public class TreeNode {
  6.  *     int val;
  7.  *     TreeNode left;
  8.  *     TreeNode right;
  9.  *     TreeNode(int x) { val = x; }
  10.  * }
  11.  */
  12. class Solution {
  13.     private static int sum, maxPathCount;
  14.     public int deepestLeavesSum(TreeNode root) {
  15.         sum = 0;
  16.         if(root == null){
  17.             return sum;
  18.         }
  19.         maxPathCount = 0;
  20.         int currPathCount = 0;
  21.         traverse(currPathCount,root);
  22.         return sum;
  23.     }
  24.     private void traverse(int currPathCount,TreeNode currNode){
  25.         if(currNode.left == null && currNode.right == null){
  26.             currPathCount++;
  27.             if(maxPathCount < currPathCount){
  28.                 maxPathCount = currPathCount;
  29.                 sum = currNode.val;
  30.             }else if(maxPathCount == currPathCount){
  31.                 sum += currNode.val;
  32.             }
  33.         }else{
  34.             currPathCount++;
  35.             if(currNode.left != null){
  36.                 traverse(currPathCount, currNode.left);
  37.             }
  38.             if(currNode.right != null){
  39.                 traverse(currPathCount, currNode.right);
  40.             }
  41.             return;
  42.         }
  43.         return;
  44.     }  
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement