Deepest Leaves Sum LeetCode solution in Java

1
class Solution {
2
  public int height(TreeNode root) {
3
    if (root == null) return 0;
4
    return Math.max(height(root.left), height(root.right)) + 1;
5
  }
6

7
  public int deepestLeavesSum(TreeNode root) {
8
    if (root == null) return 0;
9
    if (root.left == null && root.right == null) return root.val;
10
    Queue<TreeNode> q = new LinkedList<>();
11
    q.add(root);
12
    q.add(null);
13
    int hght = height(root);
14
    int sum = 0;
15
    while (q.size() > 0 && q.peek() != null) {
16
      TreeNode temp = q.remove();
17
      if (temp.left != null) q.add(temp.left);
18
      if (temp.right != null) q.add(temp.right);
19
      if (q.peek() == null) {
20
        q.remove();
21
        q.add(null);
22
        hght--;
23
      }
24
      if (hght == 1) {
25
        while (q.size() > 0 && q.peek() != null) {
26
          sum += q.remove().val;
27
        }
28
      }
29
    }
30
    return sum;
31
  }
32
}