Given a binary tree root, find the sum of the deepest node values.
Constraints
n ≤ 100,000 where n is the number of nodes in rootHint:
You need to get the sum of all the nodes at the last level of the tree. How do you traverse level by level?
GoLang: Deepest Leaves Sum via Breadth First Search
There is no inbuilt Queue object in GoLang, but we can use array/list to achieve the same task. To enque, we just need to use append method. To deque, we can use the array slicing e.g. arr[1:]. To peek the front of the queue, we can just get the value of the first element e.g. arr[0].
To compute the sum of the deepest leaves, we can use the Breadth First Search Algorithm. Let’s keep updating the sum of the current level when we expand the nodes during BFS.
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 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func deepestLeavesSum(root *TreeNode) int { if root == nil { return 0 } var Q = make([]*TreeNode, 0) Q = append(Q, root) var curSum int for len(Q) > 0 { var sz = len(Q) curSum = 0 for i := 0; i < sz; i ++ { curSum += Q[i].Val if Q[i].Left != nil { Q = append(Q, Q[i].Left) } if Q[i].Right != nil { Q = append(Q, Q[i].Right) } } Q = Q[sz:] } return curSum } |
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func deepestLeavesSum(root *TreeNode) int { if root == nil { return 0 } var Q = make([]*TreeNode, 0) Q = append(Q, root) var curSum int for len(Q) > 0 { var sz = len(Q) curSum = 0 for i := 0; i < sz; i ++ { curSum += Q[i].Val if Q[i].Left != nil { Q = append(Q, Q[i].Left) } if Q[i].Right != nil { Q = append(Q, Q[i].Right) } } Q = Q[sz:] } return curSum }
The time complexity is O(N) and so is space complexity where N is the number of the nodes in the given binary tree as we need to visit each node exactly once.
See posts of computing the sum of the deepest leaves for a given binary tree:
- Compute the Deepest Leaves Sum of a Binary Tree using BFS or DFS Algorithms
- Breadth First Search Algorithm to Compute the Sum of a Binary Tree
- GoLang: Breadth First Search Algorithm to Compute the Deepest Leaves Sum of Binary Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Rotate a 2D Matrix/Image 90 Degree Anti-Clockwise
Next Post: Teaching Kids Programming - Top Down Dynamic Programming Algorithm to Compute the Min Number of Knight Moves