Erhalten Summe von linken Blätter eines binären Baum mit Rekursion

Question

Ich habe den folgenden Code, aber es scheint in diesem Code ein Thema zu sein:

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); 
} 

Für die Eingabe [3, 9, 20, null, null, 15, 7, 2, null, null, null, 3, 2, null, null, null, 3] ich 9 den oben stehenden Code verwenden, aber die Antwort sollte 12 dh 9 + 3 sein.

Was fehlt in diesem Code?

Das Eingabearray stellt einen Binärbaum dar, in dem sich ein Elternteil an der Position i befindet, dann befindet sich sein linkes Kind unter 2 * i + 1 und das rechte Kind befindet sich unter 2 * i + 2.

Answer 1

Erstes Problem:

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

3 ist die Wurzel, es hat 9 und 20 als Kinder. 9 hat keine Kinder, 20 hat 15 und 7. Wohin gehören die 2?

Hier ist der Baum in 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 

Zweites Problem:

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); 
}