Получить сумму левых листьев бинарного дерева с помощью рекурсии

Question

У меня есть следующий код, но там, кажется, проблема в этом коде:

private boolean isLeaf(TreeNode node) { 
    if (node == null) 
     return false; 
    if (node.left == null && node.right == null) 
     return true; 
    return false; 
} 

public int sumOfLeftLeaves(TreeNode root) { 
    if (root == null) 
     return 0; 
    if (isLeaf(root.left)) 
     return root.left.val; 
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); 
} 

Для входа [3, 9, 20, null, null, 15, 7, 2, null, null, null, 3, 2, null, null, null, 3] я получаю 9 используя код выше, но ответ должен быть 12 т.е. 9 + 3.

Что отсутствует в коде?

Входной массив представляет собой двоичное дерево, где если родитель находится в позиции i, то его левый ребенок находится в 2 * i + 1, а правый ребенок - 2 * i + 2.

Answer 1

Первая проблема:

[3, 9, 20, null, null, 15, 7, 2, null, null, null, 3, 2, null, null, null, 3] 

3 является корнем, он имеет 9 и 20, как ребенок. 9 не имеет детей, 20 имеет 15 и 7. Где 2 принадлежат?

Вот дерево в Ruby:

Node (0) : 3 
    Node (2) : 20 
     Node (6) : 7 
      Node (14) : nil 
      Node (13) : nil 
     Node (5) : 15 
      Node (12) : 2 
      Node (11) : 3 
    Node (1) : 9 
     Node (4) : nil 
      Node (10) : nil 
      Node (9) : nil 
     Node (3) : nil 
      Node (8) : nil 
      Node (7) : 2 
       Node (16) : 3 
       Node (15) : nil 

Вторая проблема:

Узел может иметь лист на левой, но ветвь справа:

public int sumOfLeftLeaves(TreeNode root) { 
    if (root == null) 
     return 0; 
    if (isLeaf(root.left)) 
     return root.left.val+sumOfLeftLeaves(root.right); 
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); 
}