By Long Luo
This article is the solution 2 Approaches: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal) of Problem 1302. Deepest Leaves Sum .
Here shows 2 approaches to slove this problem: BFS (Level Order Travesal) and DFS (Get Max Depth, then Traversal).
BFS
To traverse the tree level by level , we generally use breadth first search . You can refer to this article Traverse the Tree Level by Level: Standard BFS Solution .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 public int deepestLeavesSum (TreeNode root) { if (root == null ) { return root.val; } int sum = 0 ; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelCount = queue.size(); boolean isDeepest = true ; sum = 0 ; for (int i = 0 ; i < levelCount; i++) { TreeNode curNode = queue.poll(); if (curNode.left == null && curNode.right == null ) { sum += curNode.val; } if (curNode.left != null ) { isDeepest = false ; queue.offer(curNode.left); } if (curNode.right != null ) { isDeepest = false ; queue.offer(curNode.right); } } if (isDeepest && queue.isEmpty()) { return sum; } } return sum; }
Analysis
Time Complexity : O ( n ) O(n) O ( n ) .
Space Complexity : O ( n ) O(n) O ( n ) .
DFS
Traverse the tree to find the max depth .
Traverse the tree again to compute the sum required.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public int deepestLeavesSum_dfs (TreeNode root) { int maxDepth = getMaxDepth(root); return dfs(root, 1 , maxDepth); } public int getMaxDepth (TreeNode root) { if (root == null ) { return 0 ; } return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1 ; } public int dfs (TreeNode root, int curDepth, int maxDepth) { if (root == null ) { return 0 ; } if (curDepth == maxDepth) { return root.val; } int left = dfs(root.left, curDepth + 1 , maxDepth); int right = dfs(root.right, curDepth + 1 , maxDepth); return left + right; }
Analysis
Time Complexity : O ( n ) O(n) O ( n ) .
Space Complexity : O ( m a x H e i g h t ) O(maxHeight) O ( m a x H e i g h t ) .
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗